백준 7936번 N의 존재 풀이

http://boj.kr/7936

7936번: N의 존재

n^n+n^m=a(modp)인 n이 존재하는지 찾고 존재한다면 그 숫자를 출력해야 한다.

 

x=n%p,y=n%(p-1)이라 하자. n^n=x^n,n^m=x^m으로 나타낼 수 있다. 페르마의 소정리에 의해 x^(p-1)=1(modp)이므로 x^n=x^p(modp)임을 알 수 있다. 그러므로 우리는 x^y+x^m=a(modp)를 만족시키는 음이 아닌 정수쌍 (x,y)를 찾으면 된다. CRT에 의해 (x,y)를 찾으면 항상 대응되는 n이 존재함이 보장된다.

 

식의 값은 p(p-1)을 주기로 반복된다. 그러니 p가 적당히 작을 때는 브루트포스를 이용해 직접 값을 구해줍니다. p가 작을 때 생겨나는 여러 예외들의 처리하는 부담을 덜 수 있다.

 

x를 고정해보자. p의 원시근 g를 찾고 x=g라 하자. g^y+g^m=a(modp)이다. a=g^m(modp)인 경우가 아니라면 이를 만족시키는 y를 항상 찾을 수 있다. a=g^m이라면 다른 원시근을 찾아주자. 원시근 하나가 있을 때 a^k(gcd(k,p-1)=1)로 다른 원시근들을 찾아줄 수 있다. 혹시 그런 원시근을 영원히 찾을 수 없는 경우가 있을지 궁금할 수 있는데, 이미 p가 아주 작은 경우는 처리해줬고, p가 충분히 큰 경우에는 다행히 없습니다.

 

그리고 a=g^m이 아닌 다른 원시근을 찾았다면 식을 g^y=a-g^m(modp)로 변형하고 Baby-step Giant-step 알고리즘으로 이산로그를 찾아주면 된다.

 

http://platter.tistory.com/8

Baby-step Giant step 알고리즘

 

이 알고리즘에 대한 설명은 여기에 잘 적어두었다. 여기서 설명하는 것이 바로 이산로그 문제이니 잘 보고 구현해보자. 전혀 어렵지 않다.

 

그러면 x,y 값이 모두 구해지는데, 그럼 n 값을 어떻게 복원할까요?

 

n=cp+d라 합시다. n%p=d,n%(p-1)=c+d입니다. x=d,y=c+d로 c=y-x,d=x임을 알 수 있습니다. n=(y-x)p+x임을 알 수 있고, p(p-1)에 대해 모듈러를 취해주면 끝입니다.

 

소스코드

 

http://boj.kr/92da2795247344288fb791c86ee8525d

공유 소스 보기

 

이다와 습니다의 환장적인 콜라보