백준 7936 - N의 존재

7936번: N의 존재 (acmicpc.net)

 문제 자체가 워낙 간결해서 굳이 문제를 요약할 필요는 없을 것 같다.

 우선, 정수론적인 사전지식이 몇가지 필요하다. 원시근과 이산로그에 대해 알고 있다면 해당 문제의 풀이를 이해하는데에 지장이 없을 것이다. 만약 p에 대한 원시근을 하나 찾는다면 문제가 해결되었다고도 할 수 있다. n을 p씩 올리는 행동을 n^m 항에는 어떤 영행도 미치지 않지만, n^n항에서는 지수가 정확히 1 늘어난 효과를 보여준다. 따라서 원시근을 일단 찾고 나면, n^n === a-n^m(mod p)인 문제를 해결하게 된다. 이때 n을 p씩 늘린다고 하였기 때문에, 그 원시근을 거듭해서 곱해주는 효과가 나타난다. 이 방법을 통해 특정한 값에 도달할 수 있는가는 이산로그 문제를 해결함으로써 알아낼 수 있다. 이산로그 또한 baby step giant step을 통해 충분히 빠르게 해결할 수 있다는 사실이 이미 널리 알려져 있다.

 

 다만, 원시근을 구하는 알고리즘은 생각보다 발견하기가 쉽지 않다. 그래서 본 글에서는 원시근을 빠르게 구할 수 있는 아이디어를 소개하고자 한다.

 우선, 원시근의 개수가 충분히 많다는 사실을 짚고 넘어가자. 만약 n에 대한 원시근이 존재한다면, 그것의 개수는 φ(φ(n))가 될 것이다. 만약 n이 소수라면 내부의 값은 n-1이 될 것이고, 또 오일러 파이 함수의 하계는 충분히 크다는 것이 알려져 있기 때문에 원시근의 개수가 충분히 많다고 가정할 수 있다. 따라서, 어떤 수가 원시근인지를 빠르게 판별할 수 있다면 수들을 랜덤하게 뽑음으로써 원시근을 빠르게 찾아낼 수 있다. 원시근의 판별 또한 아주 어렵진 않은데, 여기에는 폴라드-로 소인수분해가 필요할 것이다. p와 서로소인 수들의 거듭제곱은 순환군의 형태를 이루기 때문에, 이것의 위수는 p-1의 약수일 수 밖에 없다. 만약 그 위수가 p-1이 아니라면, 어떤 p-1의 소인수 q가 존재해서 그 위수는 (p-1)/q의 약수일 것이며, 따라서 원시근인지 판별하고자 하는 a에 대해 a^((p-1)/q)===1(mod p)가 성립하게 된다. 반대로 말하면, 임의의 p-1의 소인수 q에 대해 a^((p-1)/q)가 법 p에서 1이 아니라는 사실만 확인한다면 a가 원시근이라는 사실을 확신할 수 있다. 따라서 p-1을 소인수분해하는 과정에서 폴라드-로 알고리즘이 사용된다. 현재까지 적용한 모든 알고리즘들중 가장 큰 시간복잡도를 차지하는 것은 폴라드-로 알고리즘인데, 이것의 시간복잡도는 n=10^18까지에서도 빠르게 작동하기에는 충분하다. 따라서 이러한 방식을 적용하면 원시근을 구할 수 있다. 

 

 아이디어들 하나하나가 구현량을 많이 소모하고, 아이디어 자체가 워낙 많이 들어간 문제다보니 코드 길이가 무척 길어졌고, 예외처리도 진행하기 힘들었다.