[BOJ 4233] 가짜소수

문제 링크 : https://www.acmicpc.net/problem/4233

문제

페르마의 소정리 (Fermat's little theorem)의 내용은 다음과 같다.

p가 소수일 때, 임의의 정수 a>1에 대해서, a^p == a (mod p)가 성립한다.

즉, a를 p제곱한 뒤, p로 나눴을 때, 나머지는 a가 되는 것이다.

하지만, p가 소수가 아닌 경우에 어떤 정수 a에 대해서 위의 식을 만족하는 경우가 있다. 이때, p를 밑이 a인 가짜소수라고 한다. (모든 a에 대해서 식을 만족하는 수를 카마이클 수라고 한다)

p와 a가 주어졌을 때, p가 밑이 a인 가짜소수인지 아닌지 알아내는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p)

출력

각 테스트 케이스에 대해서, p가 밑이 a인 가짜소수라면 yes를, 아니라면 no를 한 줄에 하나씩 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

페르마의 소정리를 역으로 이용하여, 소수가 아니면서 특정 밑($a$)에 대해 소수와 같은 성질을 보이는 가짜소수를 판별하는 문제다. 문제의 조건에 따라 두 가지 조건을 동시에 만족해야 한다.

1. 정수 $p$가 소수가 아니어야 한다
2. $a^p \equiv a \pmod p$ 식을 만족해야 한다

$p$의 범위가 최대 $1\,000\,000\,000$으로 매우 크기 때문에, 두 조건을 효율적으로 확인하기 위해 다음과 같은 알고리즘을 사용한다.

첫째로, 소수판별법은 $O(\sqrt{p})$의 시간 복잡도를 갖는 알고리즘을 사용해도 된다. $2$부터 $\sqrt{p}$까지의 수로 $p$를 나누어보며 나누어떨어지는 수가 있는지 확인한다. $p$가 $10^9$일 때 약 $31\,622$번의 연산만으로 판별이 가능하다.

둘째로, 분할 정복을 이용한 거듭제곱(Modular Exponentiation) 알고리즘을 사용한다. 단순히 $a$를 $p$번 곱하는 것은 $O(p)$의 시간이 걸려 시간 초과가 발생하지만, 지수를 절반씩 줄여나가는 방식을 사용하면 $O(\log p)$ 안에 $a^p \pmod p$ 값을 구할 수 있다.

\[a^p \equiv a \pmod p\]

구현한 코드에서는 추가로 multiply_modular() 함수를 통해 곱셈 과정에서의 오버플로우를 방지하고 있다. 각 테스트 케이스에 대해 위의 두 조건을 확인하여 소수가 아니면서 합동식을 만족할 때만 yes를 출력하면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 소수판별법