rkm0959

관련 코드는 github에서 찾아볼 수 있다.

이 글에서 다룰 내용의 많은 부분에서 완벽한 수학적 논의는 생략할 것이다.

Miller-Rabin 소수 판별법

이 부분에 대해서는 이미 좋은 자료가 있습니다. https://casterian.net/archives/396

우리는 주어진 $n$이 소수임을 확인하고자 한다. 먼저 $n-1 = d \cdot 2^s$인 정수 $s, d$를 찾는다.

만약 $n$이 소수라면, 각 자연수 $1 \le a < n$에 대하여 다음이 성립한다.

• [P] $a^d \equiv 1 \pmod{n}$이거나, $r=0, 1, \cdots , s-1$ 중 적어도 하나에 대해 $a^{2^rd} \equiv -1 \pmod{n}$

증명을 해보자. $a^{n-1}-1 = a^{d \cdot 2^s}-1 = (a^d-1)(a^d+1)(a^{2d}+1)(a^{2^2d}+1) \cdots (a^{2^{s-1}d}+1)$이다.

그런데 페르마 소정리에 의하여 좌변은 $0 \pmod{n}$이므로, 우변 역시 $n$의 배수임을 알 수 있다.

$n$이 소수이므로, 여러 자연수의 곱이 $n$의 배수라는 것은 그 중 하나 이상이 $n$의 배수임을 의미한다. 

그러므로, $a^d \equiv 1 \pmod{n}$이거나 적당한 $0 \le r <s$가 있어 $a^{2^rd} + 1 \equiv 0 \pmod{n}$이 성립한다.

$n$이 주어졌을 때, $s, d$의 값을 계산하는 것은 쉽게 할 수 있다. 

또한, $1 \le a < n$을 만족하는 $a$가 주어졌을 때, [P]가 성립하는지 여부도 역시 빠르게 확인할 수 있다. 

이제 다음과 같은 알고리즘을 하나 고안할 수 있다.

• 테스트 횟수 $k$를 하나 정한다. $k$를 어떻게 잡는가에 대한 이야기는 나중에 한다.
• $1 \le a < n$을 만족하는 $a$를 랜덤하게 하나 잡자.
• [P]가 성립하는지 확인하자. 만약 성립하지 않는다면, $n$이 소수가 아니라는 뜻이고 알고리즘 종료.
• [P]가 성립한다면, 다시 처음으로 돌아가서 알고리즘을 반복한다. $k$번에 걸쳐 항상 [P]가 성립한다면 소수라고 판단하고 종료.

만약 $n$이 소수라면, $a$를 어떻게 잡더라도 [P]가 성립할 것이니, 무조건 소수라고 판단할 것이다.

$n$이 합성수라면 어떨까? $n$이 소수라면 [P]가 성립한다고 했지, $n$이 합성수면 무조건 [P]가 거짓이라고 하지는 않았다.

위 알고리즘이 정당한 소수 판별 알고리즘이 되려면, $n$이 합성수일 경우 높을 확률로 $n$이 소수가 아니라는 결론을 내려야 한다.

즉, $k$번의 테스트를 거쳤을 때 [P]가 거짓이 되는 $a$의 값이 매우 높은 확률로 한 번 이상 뽑혀야 한다. 이는 결국

• $n$이 합성수인 경우, [P]가 거짓이 되는 $a$가 얼마나 많은가? 

라는 문제와 동치이다. 이제 중요한 결론을 증명하지 않고 제시한다. 증명은 구글 ㄱㄱ

• $n$이 합성수인 경우, [P]가 거짓이 되는 $a$는 적어도 $3n/4$개 존재한다.
• 즉, $n$이 합성수인 경우, 한 번의 테스트를 통과할 확률은 $1/4$ 이하이다. 

이는 $k$번의 독립적인 테스트를 거쳤을 때, 합성수가 모든 테스트를 통과할 확률이 $4^{-k}$ 이하라는 뜻이다. 

그러니 $k=20$ 정도로 잡아주면 매우 높은 확률로 정답을 반환하는 좋은 소수 판별 알고리즘이 될 수 있다.

하지만 랜덤이 싫을 수 있다. 랜덤을 제거한 Miller-Rabin 알고리즘의 여러 variant가 존재한다.

• Generalized Riemann Hypothesis를 가정하면, $2 \le a < 2(\ln n)^2$를 전부 시도하면 정확하게 소수 판별을 할 수 있다.
• $n < 2^{32}$라면, $a = 2, 7, 61$인 경우만 따져보면 된다. 이때, $n = 2, 7, 61$인 경우를 따로 처리해야 함에 주의하라.
• $n < 2^{64}$라면, $a$로 $2$ 이상 $40$ 이하의 소수만 따져보면 된다. 이때, $n$ 역시 $2$ 이상 $40$ 이하의 소수인 경우에 주의하라.    

랜덤을 제거한 variant가 아마 실제 성능도 좋을 것이다. $n < 2^{64}$의 variant에서도 테스트를 12번만 하기 때문이다.

구현 노트

• 구현이 까다로운 알고리즘은 아니지만, C++의 int 범위를 넘어가는 modulus에서 여러 연산을 해야한다. 
• 특히 까다로운 것은 곱셈이다. $a, b, n$이 모두 64bit 정수일 때, $ab \pmod{n}$을 계산해야 한다.
• 이를 위해서 쓸 수 있는 첫 번째 방법은 이집트 곱셈, 즉 이진법을 사용한 곱셈이다. 이를 위해서 로그 시간이 필요하다.
• 두 번째 방법은 __int128을 동원하는 것이다. $ab$의 값을 __int128에서 계산한 뒤, $n$에 대한 나머지를 구한 후 64bit 정수로 반환한다. 
• $n$이 작으면, $\mathcal{O}(\sqrt{n})$ 알고리즘이 Miller-Rabin 알고리즘보다 빠를 수 있다. 최적화가 필요한 경우 참고하자.
• 더 적은 테스트 횟수로 $2^{64}$ 미만 자연수의 소수 여부를 판별할 수 있다. 이때, $a$ 값이 소수가 아닌 경우 "$a$의 약수인 소수"들을 특별히 고려해야 한다. 
• 위 두 가지 포인트를 추가로 고려하여 작성한 Miller-Rabin 구현체를 원한다면, 맨 위에 소개한 casterian님의 블로그를 참고하라.

Pollard-Rho 소인수분해

이 부분 역시 좋은 자료가 있습니다. https://aruz.tistory.com/140

핵심 아이디어 1. Floyd's Cycle Detection Algorithm

잠깐 전형적인 CP/PS 토픽인 그래프로 넘어오자. functional graph는 각 정점이 outdegree 1을 갖는 directed graph다.

정점 $v$가 있으면 그 정점에서 나가는 간선이 정확히 하나이니, 그 간선을 따라 도달하는 정점을 $f(v)$라 정의할 수 있다. 

즉, $f(v)$는 $v$의 "다음 정점"이다. 이제 $v \rightarrow f(v) \rightarrow f(f(v)) \rightarrow \cdots$라는 path를 생각하자.

결국 이 경로는 하나의 일직선을 그리다가, 이미 방문한 정점을 다시 방문하면서 cycle에 들어가게 될 것이다. 이 cycle을 어떻게 찾을까?

물론 여러 방법이 있겠으나, Floyd의 "토끼와 거북이" 알고리즘이 매우 효율적이다. 

• 잠시 $f^n(v) = f(f^{n-1}(v))$로 정의하자. 즉, $f^n(v)$는 $v$의 "$n$번째 뒤"의 정점이다.
• 토끼 한 마리와 거북이 한 마리를 $v$에 두자. 각 동물들의 위치를 변수 $r, t$로 명명하고 관리하겠다.
• 각 단계마다, 토끼는 두 칸, 거북이는 한 칸 이동시킨다. 즉, $r \leftarrow f(f(r))$, $t \leftarrow f(t)$를 반복한다.
• 만약 $r = t$인 시점이 오면, 사이클을 찾은 것이다. 물론, 맨 처음에 $r=t=v$인 경우는 제외하고 생각한다.

• 왜 사이클을 찾은 것인가? $k$번의 단계를 거친 후에 $r = t$임을 확인했다고 가정하자.
• 이는 $f^k(v) = f^{2k}(v)$임을 의미한다. 즉, $k$번째 뒤 정점과 $2k$번째 뒤 정점이 같다는 것을 의미한다.
• 이제 $k$번째 정점인 $f^k(v)$부터 시작하여, 다음 정점으로 이동하는 것을 반복한다. 
• 다시 시작한 $f^k(v)$에 도착할 때까지 이를 반복하면, 지금까지의 경로가 완벽하게 찾고자 하는 사이클이 된다.

• 왜 사이클이 찾아지는가? $i < j$이고 $f^i(v) = f^j(v)$인 $i, j$가 존재할 때, (즉 사이클이 있을 때) 자연수 $k$가 있어 $f^k(v) = f^{2k}(v)$임을 보이면 된다.
• "한 칸씩 격차가 벌어지는 걸 결국 사이클 길이만큼 격차가 벌어져서 다시 만났다"고 생각하면 직관적이며, 증명도 똑같다.
• 속도 차이가 나는 두 사람이 400m 트랙에서 달렸을 때, 실제로 달린 거리가 400m 차이가 나서 만날 수 있는 것과 같은 원리.
• 자세한 증명을 원한다면, $t(j-i) \ge i$인 자연수 $t$를 하나 잡고, $k=t(j-i)$라고 정의해보면 증명됨을 확인할 수 있다.

• 왜 효율적인가? 일단 시간복잡도가 (사이클 도달에 필요한 거리) + (사이클의 길이) 정도로 매우 효율적이다.
• 공간복잡도도 효율적이다. 각 정점 $v$에 대해서 $f(v)$를 계산하는데 드는 메모리를 제외하면, $\mathcal{O}(1)$만큼의 메모리가 추가적으로 필요하다.
• 특히, 여러 경우에서 $f(v)$는 진짜 간선으로 표현되는 "다음 정점"이 아니라, 말 그대로 $v$에 대한 함수가 된다. 
• 이는 아래의 경우도 마찬가지. 애초에 이름이 functional graph인 이유가 있다. 이 경우, $f(v)$를 계산하는데 드는 메모리도 $\mathcal{O}(1)$.

핵심 아이디어 2. Pseudorandom Sequence. Birthday Paradox

Birthday Paradox는 $\{1, 2, \cdots , n\}$에서 $\sqrt{n}$급 개수의 원소를 독립적으로 뽑으면, 같은 원소를 두 번 이상 뽑을 확률이 상당히 높다는 결과이다.

이는 $n=365$일 때, 대충 20~30명의 학급에서 생일이 겹치는 경우가 많다는 내용으로 알려진 결과일 것이다.

이제 우리의 목표는 주어진 합성수 $n$을 소인수분해 하는 것이다. $p$를 $n$의 가장 작은 소인수라고 하자. 우리는 $n$은 알고 있으나 $p$는 모른다.

이제 다음과 같은 방식으로 랜덤한 수열을 잡는다. $x, c$ 각각을 $1$ 이상 $n$ 미만 랜덤한 자연수라고 두자.

$x_0 = x$, $x_i = (x_{i-1}^2 + c) \pmod{n}$으로 수열을 잡자. 여기서 짚고 넘어가야 할 부분은

• 수열 $\langle x_k \rangle$은 pseudorandom. 즉, 완전 랜덤한 것은 아니지만 랜덤에 가깝다.
• $x_i$의 값은 $x_{i-1}$의 값에 의하여 완전히 결정된다. 그러니, $x_{i-1} \rightarrow x_i$를 간선으로 생각하는 functional graph를 생각할 수 있다.
• 즉, 이 수열의 값을 정점으로 갖는 functional graph를 생각할 수 있고, 마찬가지로 cycle 개념도 생각할 수 있다.
• $x_i \equiv (x_{i-1}^2 + c) \pmod{p}$ 역시 성립한다. 그러니, $y_i = x_i \pmod{p}$로 정의하면, $y_i \equiv (y_{i-1}^2 + c) \pmod{p}$이다.
• 현재 계산할 수 있는 것은 $x_i$이며, $y_i$는 실제로는 $p$를 모르기 때문에 계산할 수 없는 값이다.

이제 본격적으로 알고리즘을 설계해보자.

• $\text{gcd}(x_{2k} - x_k, n)$이라는 값을 생각해보자. 이 값을 계산하려면 $x_{2k}, x_k$의 값이 필요하며, 이는 "토끼와 거북이"의 방식으로 관리할 수 있다.
• $y_k = y_{2k}$라면, (즉 수열 $y$에서 cycle이 발견되었다면) $\text{gcd}(x_{2k} - x_k, n)$은 $p$의 배수가 된다. 
• Birthday Paradox에 의해, 이렇게 수열 $y$에서 cycle이 발견되려면 평균적으로 $\mathcal{O}(\sqrt{p})$ 정도 index가 되어야 한다. 
• 비슷하게, 수열 $x$에 대해서 cycle이 발견되려면 평균적으로 $\mathcal{O}(\sqrt{n})$ 정도 index가 되어야 한다.
• 즉, 평균적으로 $\mathcal{O}(\sqrt{p})$ 정도의 계산량 이후로 $\text{gcd}(x_{2k}-x_k, n)$이 $1$이 아닌 시점이 오며, 이때 $\text{gcd}(x_{2k}-x_k , n)$은 높은 확률로 $n$이 아니다.
• 이는 $\text{gcd}(x_{2k}-x_k, n)$이 $n$의 "nontrivial divisor"가 된다는 뜻이다. 이를 반복하면 소인수분해를 얻는다.

$n$의 non-trivial divisor를 얻기까지 평균적으로 $\mathcal{O}(\sqrt{p}) = \mathcal{O}(n^{1/4})$번의 GCD 연산이 필요하다.

구현 노트.

• 이 알고리즘에서는 random을 사용한다. C++의 rand()를 사용하기 보다는, mt19937 등을 사용하는 것을 추천한다.
• 앞에서도 언급했지만 $n$이 합성수라는 조건이 붙는다. 미리 Miller-Rabin 소수 판별을 통해 $n$이 소수인지 판별을 해야한다.
• $\text{gcd}(x_{2k}-x_k, n)=n$일 확률이 낮다고 했지, 불가능하다고 하지는 않았다. 이 경우, 시작하는 값 $x, c$를 다시 잡고 알고리즘을 다시 돌리자.
• $\text{gcd}(x_{2k}-x_k, n)=d$가 $1, n$이 아니라면, 문제를 $d$와 $n/d$를 각각 소인수분해 하는 것으로 바꿀 수 있다. 이제 재귀적으로 문제를 풀자.
• 앞에서 언급한 64bit 정수의 곱셈에 대한 내용이 여기서도 적용된다. 이집트 곱셈을 쓰거나, __int128을 사용하자.

관련 코드는 github에서 찾아볼 수 있다.

이 글에서는 팩토리얼과 이항계수를 $n$으로 나눈 나머지를 계산하는 방법에 대하여 다룬다.

• 중국인의 나머지 정리를 기반으로 한 아이디어는 여기서도 등장한다.
• $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$에 대한 나머지를 구하려면, 각 $p_i^{e_i}$에 대한 나머지를 구하면 된다.
• 그 후, 단순히 중국인의 나머지 정리를 사용하여 합쳐주면 된다. 그러니 문제를 prime power에 대해서만 해결하면 된다.

이 글에서 다룰 내용은 상당한 난이도를 갖는 강화판들이 있다. 이에 대한 것은 결과만 언급하고 링크를 걸겠다.

먼저 팩토리얼, 이항계수를 $p$로 나눈 나머지를 계산하는 방법을 알아보자. $p$는 소수.

팩토리얼

주제 1. 주어진 $n, p$에 대하여 $n! \pmod{p}$ 계산하기. 

단순히 $n! \pmod{p}$를 계산한다고 가정하자. $n \ge p$인 경우, 값은 $0$이다. 

그러니, $n < p$인 경우만 고려해도 충분하다. $n$이 작으면, $\mathcal{O}(n)$ 알고리즘이 자명하다.

$n, p$가 모두 $10^{9}$-scale로 큰 경우는, $\mathcal{O}(\sqrt{p}\log p)$ 시간에 해결할 수 있으나 상당히 어려운 문제다. 이 두 문제와 이 글 참고. 

주제 2. $1!, 2!, \cdots , n!$ 각각을 $p$로 나눈 나머지와 각각의 $\pmod{p}$에 대한 modular inverse 계산하기.

modular inverse를 계산하는 이유는 역시 이항계수를 계산하기 위해서이다. 이 주제는 수많은 카운팅 문제들에서 사용된다.

$1!, 2!, \cdots n!$ 각각을 $p$로 나눈 나머지는 점화식 $k! \equiv (k \cdot (k-1)!) \pmod{p}$를 이용하여 $\mathcal{O}(n)$ 시간에 계산할 수 있다.

팩토리얼들의 modular inverse를 구하는 것은 정말 여러 방법이 있다.

• 방법 1. 우선 각각의 modular inverse를 그냥 구하는 방법이 있다. 확장 유클리드 알고리즘을 쓰면 된다. 이 경우 $\mathcal{O}(n \log p)$의 시간 소요.
• 방법 2. $1, 2, \cdots, n$ 각각의 modular inverse를 $\mathcal{O}(n)$에 구하는 방법이 있다. 이를 사용하면 팩토리얼의 modular inverse도 똑같이 $\mathcal{O}(n)$에 ok.
• 알고리즘의 설명을 위해 프로그래밍 같은 notation을 잠시 도입한다. $i$의 modular inverse를 $inv[i]$라 하고, $a$를 $b$로 나눈 나머지를 $a \% b$라 하자.
• Fact. $2 \le i<p$이면, $inv[i] \equiv inv[p \% i] \cdot (p - \lfloor p/i \rfloor) \pmod{p}$가 성립한다. ($p$가 소수임이 필요하다)
• 증명. $p = qi + r$이라 하자. $p \% i = r$이며, $\lfloor p/i \rfloor = q$이다.
• 이제 $i \cdot inv[p \% i] \cdot (p - \lfloor p/i \rfloor) \equiv i \cdot inv[r] \cdot (p-q) \equiv inv[r] \cdot (-qi) \equiv inv[r] \cdot r \equiv 1 \pmod{p}$이므로 증명 끝.
• 여기서 $p \% i < i$이며, $inv[1]=1$임을 생각하자. 위 Fact는 결국 $inv$ 배열을 채우기 위한 DP 식이 된다. 
• $k!$의 modular inverse는 $(k-1)!$의 modular inverse와 $k$의 modular inverse를 곱해서 얻을 수 있다.
• 방법 3. 매우 쉽고 똑똑한 아이디어다. $n!$의 modular inverse를 먼저 확장 유클리드 알고리즘으로 구하자.
• 그 후, $k!$의 modular inverse가 $(k+1)!$의 modular inverse와 $(k+1)$의 곱임을 이용한다. 역순으로 계산하는 것이다.
• 이 방법으로 $1, 2, \cdots n$ 각각의 modular inverse도 $\mathcal{O}(n)$ 시간에 구할 수 있다. 
• $k$의 modular inverse를 구하려면, $k!$의 modular inverse와 $(k-1)!$을 곱하면 된다.

방법 2, 3은 둘 다 $\mathcal{O}(n)$ 알고리즘이다. 하나만 알아도 충분하지만, 극한의 시간 최적화가 필요한 경우에는 둘 다 알아야 한다.

• 만약 $1, 2, \cdots , n$ 각각의 modular inverse를 얻는 것이 주요 목적이라면, 방법 2를 사용하는 것이 맞다.
• 만약 $1!, 2!, \cdots, n!$ 각각의 modular inverse를 얻는 것이 주요 목적이라면, 방법 3을 사용하는 것이 맞다.
• 위에서 언급한 modular inverse들을 전부 구하는 것이 목적이라면, 어느 것을 사용해도 문제가 없다.
• 이유를 파악하기 위해서는 각 방법들이 언급한 값들을 계산하기 위해서 몇 번의 나머지 연산을 하는지 생각해보자.

개인적인 추천은 그냥 방법 2, 3을 다 알고 있는 것이다. 방법 2의 원리까지는 이해할 필요가 없으니, 코드만 알아두면 된다.

주제 3. $n! = p^e m$라고 쓸 경우 (단, $m$은 $p$의 배수가 아니다) $e$와 $m \pmod{p}$를 계산하기.

이는 일종의 "$n!$의 0이 아닌 마지막 자리 구하기"와 같은 부류의 문제라고 볼 수 있다. 이 문제를 $p$진법에서 푸는 것이기 때문.

이 문제가 필요한 이유는 이항계수의 계산이다. $n!$이 $p$의 배수라고 해서 $\binom{n}{k} =n!/(k!(n-k)!)$이 $p$의 배수일 이유는 없다.

$n < p$인 경우는 $e=0$이며, $m \pmod{p}$는 단순히 $n! \pmod{p}$이다. 그러니 앞선 논의를 그대로 사용할 수 있다.

사실 이 말은 주제 3의 문제가 주제 1의 문제를 포함하고, 더 어려운 문제라는 이야기다. 그러니 $p$가 크면 이 문제도 풀기 힘들 것이라고 예측할 수 있다.

여기서 다룰 경우는 $p$가 $\mathcal{O}(p)$ 알고리즘이 돌아갈 정도로 작고, $n$은 매우 클 수 있는 경우이다.

여기서도 문제를 축소하는 방법을 사용할 것이다. $n=pk+r$, $0 \le r < p$라고 하자. 아래 그림과 함께 보자.

• $1$부터 $n$까지의 수 중, $p$의 배수가 아닌 것에 먼저 집중하자.
• $[1, p-1], [p+1, 2p-1], \cdots , [p(k-1)+1, pk-1], [pk+1, pk+r]$ 형태의 구간으로 나누어 볼 수 있을 것이다.
• 첫 $k$개의 구간을 보자. 각 구간에 있는 정수들을 곱한 값은 $(p-1)! \pmod{p}$이다. (사실 이는 $-1 \pmod{p}$다. 윌슨의 정리)
• $[pk+1, pk+r]$의 구간에 있는 정수들을 곱한 값은 $r! \pmod{p}$이다. 
• 이제 $p$의 배수들인 것에 집중하자. $p, 2p, \cdots , kp$가 있다. 여기서 $p$를 $k$개 뽑아낼 수 있다.
• 그러면 남는 것은 $1, 2, \cdots , k$고, 이는 정확히 $k!$과 같다. 여기서 우리는 문제를 $k!$에 대한 문제로 축소시켰다.
• $k!$을 $p^{e'} m'$으로 쓸 때, $e'$와 $m' \pmod{p}$의 값을 알아냈다고 가정하자. 이제 $n! = p^e m$이라 쓸 때 $e$와 $m \pmod{p}$를 구할 수 있을까?
• 가능하다. 위 논의를 정리하면, $e = e' + k$, $m \equiv m' \cdot (p-1)!^k \cdot r! \pmod{p}$를 반환하면 된다.
• 앞에서도 언급했지만 $(p-1)! \equiv -1 \pmod{p}$이므로, $m$을 계산할 때는 $k$의 홀짝성만 봐도 충분하다.
• 당연히 구현은 재귀적으로 하는 것이 편하다. 또한, 알고리즘을 돌리기 전 $1!, 2!, \cdots , (p-1)! \pmod{p}$를 전처리하는 것이 좋다. 
• 문제가 얼마나 축소되는가? : $n$에서 $k$로 축소시켰고, $k \le n/p \le n/2$이다. 그러니 반 이상 감소하고, 로그 시간에 ok.
• 여러분도 눈치챘겠지만, 여기서 $e = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots $임을 얻는다.

이항계수

이제 이항계수 $\binom{n}{k}$를 $\pmod{p}$에 대하여 계산하는 방법을 보자. $\binom{n}{k} = \binom{n}{n-k}$이니, $k \le n/2$만 보자. 여러 경우가 있다.

Case 1. $k<p$이며 $k$가 작은 경우. 

이 경우, $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{1 \cdot 2 \cdots k}$임을 이용하여 직접 계산을 할 수 있다.

분자, 분모를 모두 $\pmod{p}$로 구한 후, 분모의 modular inverse를 구해 나눗셈을 곱셈으로 대체한다. 

물론, $k<p$이므로 $\text{gcd}(k!,p)=1$이며, 그러니 확장 유클리드 알고리즘으로 modular inverse를 구할 수 있다.

사실, $\displaystyle \binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$이 성립함을 이용하여 더 많은 것을 할 수 있다.

위 식을 차례대로 적용하여, 단순히 $\binom{n}{k} \pmod{p}$를 구하는 것이 아니라 $\binom{n}{0}, \binom{n}{1}, \cdots , \binom{n}{k}$ 각각을 $p$로 나눈 나머지를 구할 수 있다.

Case 2. 작은 $n, k$에 대하여 전부 전처리를 하고 싶은 경우.

이 경우, 파스칼의 삼각형을 이용하여 DP와 같은 방식으로 계산을 할 수 있다. 정수론이 필요없는 영역이다.

Case 3. $p$가 작은 경우, 즉 $\mathcal{O}(p)$ 알고리즘이 동작할 수 있는 경우.

먼저 $1!, 2!, \cdots , (p-1)!$ 각각을 $p$로 나눈 나머지와, 그들의 modular inverse를 전처리하자.

방법 1. Lucas 정리 사용

많이 사용되는 방법 중 하나다. 다음 결과를 증명하지 않고 제시한다. 증명은 위 링크에 걸려있다. 

정리. $m = m_km_{k-1} \cdots m_0$, $n=n_k n_{k-1} \cdots n_0$가 $m, n$의 $p$진법 전개라면, $\displaystyle \binom{m}{n} \equiv \binom{m_k}{n_k} \cdot \binom{m_{k-1}}{n_{k-1}} \cdots \binom{m_0}{n_0} \pmod{p}$다.

증명의 아이디어가 (Frobenius Endomorphism) 문제 풀이에 사용된 걸 본 적이 없는 것은 아니나, 모두 매우 어려운 문제들이다.

이 결과는 문제를 단순히 $m, n$이 $p$ 미만일 경우에 $\binom{m}{n} \pmod{p}$를 계산하는 문제로 만들어준다.

$m<n$인 경우 결과는 $0$이며, 그렇지 않은 경우 $m!/(n!(m-n)!)$을 계산하여 답을 얻을 수 있다.

이제는 어느 정도 당연한 이야기지만, 나눗셈은 modular inverse를 곱하는 것으로 계산한다.

전처리를 했기 때문에, 각 $\binom{m_i}{n_i} \pmod{p}$를 구하는 것에는 $\mathcal{O}(1)$의 시간이 필요하다.

그러니 시간복잡도는 $\mathcal{O}(k) = \mathcal{O}(\log_p m)$이 되겠다. 매우 빠르고 간단한 방법이다. 

방법 2. 앞서 다룬 주제 3 사용

주제 3을 이용하여도 문제를 해결할 수 있다. $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$이라 하자.

이제 $n! = p^{e_1} m_1$, $k! = p^{e_2} m_2$, $(n-k)!=p^{e_3} m_3$라고 쓰자. $m_1, m_2, m_3$는 $p$의 배수가 아니다.

이때, 주제 3에서 다룬 알고리즘으로 $e_1, e_2, e_3$와 $m_1, m_2, m_3 \pmod{p}$를 로그 시간에 계산할 수 있다.

그러면 이제 $\displaystyle \binom{n}{k} =  p^e m$이라 쓸 때, $e$와 $m \pmod{p}$를 구할 수 있을까?

있다. $e = e_1 - e_2 - e_3$, $m \equiv m_1 (m_2m_3)^{-1} \pmod{p}$가 성립하기 때문이다. $a^{-1}$은 $a$의 잉여역수.

만약 $e>0$이라면 주어진 이항계수는 $p$의 배수가 된다. 그렇지 않다면, 이항계수를 $p$로 나눈 나머지는 $m \pmod{p}$와 같다. 끝.

이제 $\pmod{p}$의 논의를 끝냈다. 이제 본격적으로 prime power에 대하여 논의해보자. 

팩토리얼

주제 1. 주어진 $n, p$에 대하여 $n! \pmod{p^e}$ 계산하기.

$n \ge pe$이면 $n!$에서 $p$의 배수가 $e$개 이상 들어가므로, $n! \pmod{p^e}$는 $0$이 된다. 

$n$이 작으면 단순한 $\mathcal{O}(n)$ 알고리즘이 작동한다는 점은 기존 주제 1의 논의에서와 동일하다. 

주제 2. $1!, 2!, \cdots , n!$ 각각을 $p^e$로 나눈 나머지와 각각의 $\pmod{p^e}$에 대한 modular inverse 계산하기.

문제가 잘 정의되려면 역시 $n < p$를 가정해야 한다. 이 경우, 방법 1과 방법 3이 잘 적용된다. 

주제 3. $n! = p^t m$라고 쓸 경우 (단, $m$은 $p$의 배수가 아니다) $t$와 $m \pmod{p^e}$를 계산하기.

$t$를 계산하는 것은 기존 주제 3과 애초에 목표가 동일하다. $m \pmod{p^e}$를 계산하는 것이 목표. 이 역시 기존 주제 3과 비슷한 방법으로 할 수 있다.

• 쉽게 가자. $n=pk+r$, $0 \le r < p$라고 쓰자. 
• $1$부터 $n$까지의 수 중, 이번에는 $p$의 배수인 것에 먼저 집중해보자.
• 여기서는 $p$가 $k$개 추가되고, $k!$이 튀어나온다. 이는 문제의 "축소"된 형태이다. 여기까진 기존 주제 3과 동일.
• 이제 $p$의 배수가 아닌 것을 봐야 한다. 잠시 $n=p^ek' + r'$이라고 하자. $0 \le r' < p^e$. 
• $\mathcal{O}(p^e)$의 시간을 투자하여, DP를 이용해 다음 배열 $val[i]$를 ($0 \le i < p^e$) 채워놓자. 미리 전처리하는 것이다.
• $val[i]$ : $1$ 이상 $i$ 이하 자연수 중 $p$의 배수가 아닌 것을 곱한 값을 $p^e$로 나눈 나머지.
• $[1, p^e-1]$ 중 $p$의 배수가 아닌 것부터 $[p^e(k'-1)+1, p^ek'-1]$ 중 $p$의 배수가 아닌 것이 먼저 있을 것이다.
• 그 후 $[p^ek'+1, p^ek'+r']$ 중 $p$의 배수가 아닌 것이 여기에 있다. 이를 모두 종합하면?
• $val[p^e-1]^{k'} \cdot val[r'] \pmod{p^e}$이라는 값이 튀어나온다. 결국 기존 주제 3과 거의 다를 바가 없다. 
• 또한, $val[p^e-1]$이 $\pmod{p^e}$로 $1$ 또는 $-1$이라는 결과 역시 알려져 있다. 그러니 $k'$의 홀짝성만 봐도 ok.

이 알고리즘은 $\mathcal{O}(p^e)$ 급의 계산이 필요하다. 하지만 실제로는 $\mathcal{O}(pe)$ 급으로 계산이 가능하다. 매우 어렵다.

이 강화된 알고리즘을 공부하고 싶다면, HYEA님의 이 글과 원본이라고 볼 수 있는 min_25의 이 글을 보자.

이항계수

여전히 $k \le n/2$만 보는 아이디어는 유효하다.

Case 1. $k<p$이며 $k$가 작은 경우. 

이 경우, $1, 2, \cdots , k$ 각각의 $\pmod{p^e}$에 대한 modular inverse가 존재하므로 아이디어가 그대로 적용된다.

Case 2. 작은 $n, k$에 대하여 전부 전처리를 하고 싶은 경우.

이 경우, 파스칼의 삼각형을 이용하여 DP와 같은 방식으로 계산을 할 수 있다. 정수론이 필요없는 영역이다.

Case 3. $p$가 작은 경우, 즉 $\mathcal{O}(p^e)$ 또는 $\mathcal{O}(pe)$ 알고리즘이 동작할 수 있는 경우.

이 문제를 Lucas 정리로 풀려고 하면 (즉, Lucas 정리의 확장판을 찾으려 한다면) 상당히 고생할 것이다. 적어도 내 기억은 즐겁지 않았다.

하지만 주제 3을 이용한 풀이를 생각한다면, 기존 Case 3과 완전히 동일한 풀이가 적용된다. 주제 3을 여기에 수록한 이유다.

이제 $\pmod{p^e}$에 대한 이야기를 끝냈으니, 이론적으로 모든 내용을 다 했다. 하지만 몇 가지 더 이야기거리가 남았다.

• 중국인의 나머지 정리는 항상 강조하지만 수학에서나 정수론 알고리즘에서나 매우 중요한 결과고 쓸모도 많다.
• 하지만 이걸 제대로 써먹으려면 (즉, prime power로 문제를 쪼갠 후 다시 합치는 방식을 적용) 소인수분해를 해야 한다.
• 기본적으로 소인수분해는 매우 어려운 문제다. CP/PS 환경에서는 보통 커봐야 $2^{64}$인 수를 다루니 Pollard-Rho 알고리즘을 배우면 조금 낫다.
• 하지만 Pollard-Rho가 엄청 빠른 알고리즘인 것도 아니다. 즉, 일반적인 $\pmod{M}$에 대해서 사용할 수 있는 알고리즘을 더 다룰 필요가 있다.
• 당연한 것이지만 아래에서 다룰 "일반적인 알고리즘"은 위에서 다룬 $\pmod{p}$, $\pmod{p^e}$의 경우에서도 사용할 수 있다. 
• 아래에서 다룰 알고리즘들은 modulus가 갖는 소인수 $p$나 prime power $p^e$의 크기 등에 영향을 받지 않는다.

팩토리얼

주제 1. $\mathcal{O}(n)$ 알고리즘은 당연히 아직도 유효하다.

주제 2. 팩토리얼만 구하는 $\mathcal{O}(n)$ 알고리즘은 당연히 아직도 유효하다.

modular inverse를 전부 구하는 문제가 잘 정의되려면 $1, 2, \cdots , n$이 전부 $M$과 서로소여야 한다.

이 경우, 방법 1, 3이 잘 적용된다. (소수, 소수의 거듭제곱 여부를 사용한 적이 없다)

주제 3. 일반적인 modulus $M$에 대해서 논의하기 애매한 주제다. 이 때문에 이항계수를 계산하기가 어렵다.

이항계수

Case 1. $k$가 작고, $1, 2, \cdots , k$ 전부가 $M$과 서로소인 경우.

이 경우에는 기존 알고리즘을 그대로 적용할 수 있다. $\pmod{M}$에 대한 modular inverse를 취할 수 있기 때문이다.

Case 2. 파스칼의 삼각형을 그대로 적용할 수 있다. 이미 말했지만, 이 부분은 정수론이 아니라 DP에 가깝다.

Case 3. 하기 힘들다. 애초에 각 소수가 작다는 가정이 전제되는 만큼, 소인수분해가 필요하다.

Case 4. 특수한 경우를 하나 더 소개한다. 바로 $n, k$가 둘 다 적당히 작은 경우다.

이 경우, 앞서 소개한 에라토스테네스의 체를 이용한 로그 시간 소인수분해를 하여 문제를 해결할 수 있다.

즉, $1, 2, \cdots , n$ 전부를 소인수분해 할 수 있으니, $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1) \cdots \cdot ( n-k+1)}{1  \cdot 2 \cdots \cdot k}$ 역시 그 분모/분자를 전부 소인수분해 할 수 있다.

이를 통해서 아예 $\displaystyle \binom{n}{k}$의 소인수분해를 얻을 수 있다. 이제 나눗셈에 대한 걱정이 아예 없으니, 단순 계산이 가능해진다. 끝.

다음 정리들은 정수론의 기초적이고 중요한 결과들이다. 증명은 찾아보면 쏟아져 나온다. 혹시 필요하면 댓글 :)

• 페르마의 소정리. 소수 $p$와 자연수 $a$가 $\text{gcd}(a, p)=1$을 (즉, $a$는 $p$의 배수가 아니다) 만족하면 $a^{p-1} \equiv 1 \pmod{p}$. 
• 오일러 정리. 앞서 오일러 파이 함수를 정의했다. 사실 $\phi(n)$은 $n$ 이하이며 $n$과 서로소인 자연수의 개수이다. 
• 오일러의 정리는, 자연수 $n, a$가 $\text{gcd}(a, n)=1$을 만족할 경우, $a^{\phi(n)} \equiv 1 \pmod{n}$임을 말한다. 페르마의 소정리는 특수 케이스.

잠깐 오일러 파이 함수에 대한 기본 사실들을 빠르게 짚고 넘어가자. 증명은 검색하면 충분히 나올듯. 필요하면 댓글 :)

• 앞서 언급했듯이, $n$의 서로 다른 소인수가 $p_1, p_2, \cdots , p_k$라면 $\phi(n) = n(1-1/p_1)(1-1/p_2) \cdots (1-1/p_k)$이다. 
• $\phi$는 multiplicative function이다. 이는 $n, m$이 서로소인 자연수일 때, $\phi(nm) = \phi(n)\phi(m)$임을 의미한다.
• $m|n$이면 $\phi(m)| \phi(n)$ 역시 성립한다. 이 사실은 이 단원에서 사용될 것이다.
• 이 외에도, $\sum_{d|n} \phi(d) = n$ 등 재밌는 성질이 많다. $\sum_{d|n}$이란, $n$의 약수 $d$에 대하여 더한다는 뜻.

그런데 생각보다 이 정리들을 CP/PS 환경에서 사용할 곳을 떠올리기는 쉽지 않다. 

•  보통 많이 쓰이는 방식은 $p$가 소수일 때, $\pmod{p}$에서 $a$의 ($a, p$는 서로소) modular inverse를 구하는 것이다.
•  즉, $a^{p-1} \equiv 1 \pmod{p}$에서 $a^{p-2} \cdot a \equiv 1 \pmod{p}$를 얻고, $a^{p-2}$가 modular inverse임을 얻는 것이다.
• 하지만 우리가 앞에서 살펴보았듯이, modular inverse를 구하는 것은 소수가 아닌 경우에도 쓸 수 있는 일반적이고 빠른 방법이 있다.
• 페르마의 소정리는 그렇다 쳐도, 오일러 정리는? modular inverse를 오일러 정리로 구하려면 $\phi(n)$ 값이 필요하다.
• $\phi(n)$을 구하려면 기본적으로 $n$의 소인수분해가 필요하다. $n$이 $10^9$-scale로 큰 경우에는 에라토스테네스의 체도 쓸 수 없으니, 진짜 소인수분해를 해야한다. 이때 시간복잡도는 현재 지식상으로는 $\mathcal{O}(\sqrt{n})$. 로그 시간을 보장하는 확장 유클리드와 비교된다. 그러면 어디서 쓸까?
• 물론, 오일러 파이 함수 자체는 CP/PS 환경에서 많이 쓰인다. 카운팅 문제에서 Burnside's Lemma 등을 활용할 때도 사용되고, 후에 다룰 내용에도 등장한다. 애초에 쓸모가 엄청 많은 함수다. 여기서 사용할 곳이 적다고 말하는/주장하는 것은 오일러 정리의 활용이다.
• (물론, 이렇게 말하지만 오일러 정리도 PS에서 아래에서 설명하는 예시 외의 문제에서 쓰이지 않는 것은 당연히 아니다)

보통 CP/PS에서 (그리고 사실 예전 KMO 1차에서) 이러한 정리들을 사용하는 환경은, "Power Tower"를 계산하기 위한 것이다. 대충 이런 문제다. 

모두의 편의를 위하여 $[a_1, a_2, \cdots , a_k] = a_1^{a_2^{ \cdots ^{a_k}}}$라고 정의하자. 우리의 목표는 $[a_1, a_2, \cdots , a_k] \pmod{n}$을 효율적으로 계산하는 것이다.

또한, 편의상 Power Tower $[a_1, a_2, \cdots, a_k]$의 길이를 등장하는 자연수의 개수 $k$라고 정의하겠다.

원리에 특별히 관심이 없고 알고리즘 및 시간복잡도만 필요한 분들은, 마지막 문단으로 바로 넘어가도 된다. 그래도 한 번 다 읽어보는 것을 추천. 

상대적으로 간단한 경우부터 보자. $\text{gcd}(a_1, n) = 1$을 가정한 상태에서 생각을 해보자. 오일러 정리에 의하여, 우리는 $a_1^{\phi(n)} \equiv 1 \pmod{n}$을 알고 있다. 

그러므로, $a_1$을 밑으로 할 때 지수에 $\phi(n)$에 대한 나머지를 취해도 결과값의 $n$에 대한 나머지가 변하지 않는다.

즉, $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k]} \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \pmod{n}$가 성립할 것이다. 이 식의 의미하는 바는 결국

• $a_1, \cdots , a_k, n$에 대한 문제를 $a_2, \cdots, a_k, \phi(n)$으로 간단하게 "축소", "환원"할 수 있다.

라는 것이다. 왜 "축소"일까? 이를 바라보는 것에는 두 가지 관점이 가능하다. 

• Power Tower의 "길이"가 $k$에서 $k-1$로 축소되었다고 볼 수 있다.
• $\phi(n) < n$은 ($n \neq 1$이면) 앞서 언급한 $\phi$의 성질/정의에서 자명하다. 그러니 modulus가 $n$에서 $\phi(n)$으로 축소되었다고 볼 수 있다.

어느 관점으로 보는 게 좋을까? 첫 번째 관점은 단순히 $\mathcal{O}(k)$의 횟수로 끝남을 의미할 뿐이다. 두 번째를 보자.

• 사실 1. $\phi(n)$은 $n \ge 3$에 대하여 모두 짝수이다. $\phi(n)$은 $1$ 이상 $n$ 이하 자연수 중 $n$과 서로소인 것의 개수라고 했었다. 그런데 $\text{gcd}(a, n)=1$이면 $\text{gcd}(n-a, n) = 1$도 성립한다. (갑자기 이해가 안된다면, 유클리드 알고리즘 부분을 다시 한 번 읽고 오는 것을 추천한다) 그러니 $a$와 $n-a$를 (합이 $n$인) 한 쌍으로 묶을 생각을 할 수 있다. 이렇게 묶이지 않는 경우는 $n$이 짝수일 때 $n/2$ 뿐이다. 그런데 $n \ge 3$이므로 $n$이 짝수이면 $\text{gcd}(n/2, n) = n/2 > 1$이 되고, 이 경우는 고려할 필요가 없음을 알 수 있다. 그러니 쌍을 전부 맺어줄 수 있고, 개수는 짝수.
• 사실 2. $n$이 짝수이면, $\phi(n) \le n/2$이다. $2$ 이상 $n$ 이하 모든 짝수들이 $n$과 공통 소인수 $2$를 가지므로, $n$과 서로소가 될 수 없다. 그러니 서로소인 것의 개수는 많아봐야 $n-n/2 = n/2$개이며, 증명 끝. 이 두 사실을 이용하여, 우리가 문제를 "축소"하는 방식이 매우 강력함을 보여보자.

우리의 두 번째 관점은 modulus $n$의 감소에 집중하고 있다. $n$이 작으면 문제가 확실히 간단해진다.

$n=2$라면, $a_1$의 홀짝성만 판단하여 답을 바로 결정할 수 있다. $n=1$이면 그냥 답이 $0$이다. 그러니, 목표는 결국

• $n \rightarrow \phi(n) \rightarrow \phi(\phi(n)) \rightarrow \cdots $를 거칠 때, 언제 $1$이 될 것인가?

가 된다. 이러한 과정이 많아봐야 $\mathcal{O}(\log n)$번 필요함을 보이자.

• $n \rightarrow \phi(n)$ 과정에서는 별 논의를 할 수 없지만, 적어도 $\phi(n) < n$임은 안다.
• 그 이후부터는 재밌어진다. 사실 1에 의하여, 현재 $\phi(n)$은 짝수거나 $\phi(1)=\phi(2)=1$이다.
• $\phi(n)=1$인 경우에는 그냥 끝이다. $\phi(n)$이 짝수라 가정하자. 사실 2에 의하여, $\phi(\phi(n)) \le \phi(n)/2$이다.
• 즉, 한 번 과정을 거치면 modulus가 무조건 반 이상 감소한다. 이제 많아봐야 로그 횟수의 과정이 필요함은 당연하다.

물론, 위 논의는 문제를 축소하는 과정에서 계속 밑과 modulus가 서로소라는 가정이 성립할 때 가능한 것이다. 

즉, 처음에는 $\text{gcd}(a_1, n)=1$이어야 하며, 그 뒤에는 $\text{gcd}(a_2, \phi(n))=1$, $\text{gcd}(a_3, \phi(\phi(n)))=1$ 등이 필요하다.

이 가정을 제거하고 일반적인 문제를 해결하려면, 많은 노력이 필요하다. 우선 빠르게 전처리를 하나 하자.

• 이제부터 $a_i \ge 2$가 각 $i$에 대하여 성립함을 가정한다. $1$은 몇 번 곱해도 $1$이므로, $[a_1, a_2, \cdots, a_k , 1, b_1, b_2, \cdots, b_t] = [a_1, a_2, \cdots, a_k]$가 항상 성립한다. 즉, $1$이 등장하면 그 $1$과 뒤에 있는 tower를 다 날려도 된다. 이렇게 쓸모없는 부분을 날리는 과정을 거치면, $a_i \ge 2$인 상태가 된다. 

이제 다시 문제를 축소할 준비를 하자. $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots,  a_k]} \pmod{n}$는 정의상 여전히 성립.

문제를 해결할 각을 천천히 재보자. 개인적인 생각으로, 핵심 아이디어는 다음과 같다.

• 아이디어 1. 중국인의 나머지 정리와 소인수분해 : 사실 앞 단원에서 해도 되는 이야기지만, 여기서 한다. 
• 소인수분해는 자연수 $n$을 적당한 서로 다른 소수 $p_1, \cdots , p_k$에 대하여 $p_1^{e_1} p_2^{e_2} \cdots  p_k^{e_k}$ 형태로 유일하게 쓸 수 있다는 결과이다.
• 중국인의 나머지 정리는 $x \pmod{p_1^{e_1}}, x \pmod{p_2^{e_2}}, \cdots , x \pmod{p_k^{e_k}}$를 알면 이를 합쳐서 $x \pmod{n}$을 얻을 수 있다는 결과이다.
• 물론 반대 방향도 마찬가지. 즉, $n$에 대한 나머지를 아는 것과 $p_1^{e_1}, p_2^{e_2}, \cdots , p_k^{e_k}$에 대한 나머지를 아는 것은 완벽하게 동치이다.
• 그러니 $n$을 소인수분해하고, $n$이 갖는 각 prime power $p^e$에 대하여 $a_1^{[a_2, \cdots, a_k]} \pmod{p^e}$를 구할 생각을 할 수 있다.
• 이 생각의 흐름은 순수하게 수학적으로 보나, 지금/나중에 다룰 알고리즘의 중간 과정으로 보나 매우 중요하다. 

• 아이디어 2. 소수에 대한 케이스 분류 : 이제 목표를 $a_1^{[a_2, \cdots , a_k]} \pmod{p^e}$를 계산하는 것으로 정했다.
• Case 1. $a_1$이 $p$의 배수가 아닌 경우. 이 경우에는 $\text{gcd}(a_1, p^e)=1$이므로 기존에 했던 것과 똑같이 할 수 있다. 
• 즉, $[a_1, a_2, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(p^e)}} \pmod{p^e}$가 성립한다.
• Case 2. $a_1$이 $p$의 배수인 경우. 이 경우가 우리가 새롭게 다루어야 하는 경우라고 볼 수 있겠다.
• 이 경우, $[a_2, \cdots , a_k]$의 값이 중요하다. 당장 이 지수가 $e$ 이상이라면, $a_1^{[a_2, \cdots, a_k]}$는 $p^e$의 배수가 된다.
• 그러니, 우리가 고안해야 하는 것은 $[a_2, \cdots, a_k]$가 $e$ 이상인지 판별하고, 아니라면 실제 값이 얼마인지 구하는 알고리즘이다.
• 길이 $4$의 Power Tower만 해도 $[2, 2, 2, 2] = 2^{16}$이므로, 이는 (CP/PS 환경에서) 커봐야 $60$ 언저리일 $e$를 훌쩍 넘는다.
• 즉, 길이 $3$ 이하의 Power Tower에 대해서만 고려해도 된다. 이제부터는 정수론이 아닌 단순 알고리즘의 영역이니, 직접 고민해보는 것 추천.
• 어쨌든 이 과정에서 $a_1^{[a_2, \cdots , a_k]} \pmod{p^e}$를 구할 수 있다. 각 경우에서 해답을 얻었으니, 중국인의 나머지 정리로 합치면 된다.

위 알고리즘은 어쨌든 문제를 환원하는 알고리즘이고, 실제로도 잘 작동할 것이다. 하지만 좀 복잡하고 더러우니, 깔끔하게 바꿔보자.

• 보조정리. $m|n$이면, $a \equiv (a \pmod{n}) \pmod{m}$이 성립한다. 
• 증명. $a \pmod{n}$은 어쨌든 적당한 정수 $k$에 대하여 $a+kn$으로 쓸 수 있다. $(a+kn)-a=kn$은 $m$의 배수이므로 증명 끝.

다시 아이디어 2의 케이스 분류 중 첫 번째 케이스로 돌아가보자. 

• Case 1. $a_1$이 $p$의 배수가 아닌 경우.
• $p^e|n$이므로, $\phi(p^e)|\phi(n)$이다. 보조정리에서 $([a_2, \cdots , a_k] \pmod{ \phi(n)}) \equiv [a_2, \cdots , a_k] \pmod{\phi(p^e)}$다.
• 그러므로, 오일러 정리에서 $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \pmod{p^e}$가 성립한다.
• 이는 문제를 $n \rightarrow \phi(p_1^{e_1}), \phi(p_2^{e_2}), \cdots , \phi(p_k^{e_k})$로 복잡하게 문제를 환원하지 않고, 기존처럼 $n \rightarrow \phi(n)$ 형태로 문제를 환원할 수 있음을 의미한다.
• 즉, $[a_2, \cdots , a_k] \pmod{\phi(n)}$만 구하면 별다른 추가적인 처리 없이 원하는 계산을 할 수 있다는 의미다. 

이제부터 $[a_2, \cdots , a_k]$의 크기에 대한 케이스를 나눈다. 

• $[a_2, \cdots , a_k]$가 $100$ 이하인 경우. 이 경우에는 애초에 Power Tower의 길이 $k-1$이 $3$ 이하임을 앞에서 설명하였다. 그러니 $[a_2, \cdots,  a_k]$를 직접 계산한 뒤, $a_1^{[a_2, \cdots , a_k]} \pmod{n}$을 계산하면 된다. 즉, 이 경우는 중국인의 나머지 정리, 소인수분해, 앞선 케이스 분류 등의 아이디어가 필요없다.
•  $[a_2, \cdots , a_k]$가 $100$ 초과인 경우. 이 경우에는 $p|a_1$인 소수 $p$들에 대하여, $p^e$가 $n$의 prime power인 경우 ($e \le 100$일테니) $[a_1, a_2, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k]} \equiv 0 \pmod{p^e}$가 될 것이다. 물론, $a_1$이 $p$의 배수가 아닌 경우는 위에서 다루었다.

이제 다음을 보일 준비가 완료되었다.

• Claim. $[a_2, \cdots , a_k] > 100$인 경우, $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{n}$이다.
• 중국인의 나머지 정리를 생각하면, 결국 $n$의 소인수분해에 등장하는 각 prime power $p^e$에 대해 양변이 같은 나머지를 가짐을 보이면 된다.
• Case 1. $a_1$이 $p$의 배수가 아닌 경우. $\phi(p^e)|\phi(n)$이 성립하므로, 오일러의 정리에서 (즉, $a_1^{\phi(p^e)} \equiv 1 \pmod{p^e}$)
• $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{p^e}$다. 증명 끝.
• Case 2. $a_1$이 $p$의 배수인 경우. $e \le 100$이고, $[a_2, \cdots , a_k] \ge 100$이고, $100 \cdot \phi(n) \ge 100$이다. 
• 그러니, $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots, a_k]} \equiv  0 \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{p^e}$다. 증명 끝.

위의 $100$이라는 값은 CP/PS 환경을 가정한 것이다. 실제로는 modulus가 $n$일 때, $\log_2 n$ 초과인 값을 아무거나 잡으면 된다. (너무 크게 잡으면 고생한다)

CP/PS 환경에서 웬만하면 $2^{100}$을 넘는 modulus는 볼 수 없을 것이므로, 그냥 $100$이라고 잡았다. 이렇게 하는 것이 짜기도 편하다.

이제 알고리즘을 정리해보자. 

• 입력은 $a_1, \cdots , a_k$와 $n$. $[a_1, \cdots , a_k] \pmod{n}$을 푸는 것이 목표다. 단, $a_i \ge 2$를 가정한다.
• 만약 $k \le 4$라면, $[a_2, \cdots , a_k]$가 $100$ 이하인지 판별하는 과정을 거친다.
• 만약 $100$ 이하라면, $[a_2, \cdots , a_k]$를 직접 계산하고 $a_1^{[a_2, \cdots , a_k]} \pmod{n}$을 반환한다.
• 그렇지 않다면, $\phi(n)$을 계산해준 뒤, $[a_2, \cdots , a_k] \pmod{\phi(n)}$을 계산한다. (즉, $a_2, \cdots , a_k$와 $\phi(n)$에 대한 문제를 푼다.)
• 그 후 $a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{n}$을 반환한다. 끝.

$a_i$가 $1$이 되어도 빠르게 잘 작동하는 알고리즘을 구축하는 것은 여러분의 몫이다. (정수론적 내용/테크닉이 추가되지 않는다) 

이 알고리즘은 맨 처음 여러 가정을 추가한 경우의 알고리즘처럼, modulus를 $n$에서 $\phi(n)$으로 축소한다.

이 과정이 로그 번 반복된 후에 modulus가 $1$이 된다는 사실은 그 때와 달라지지 않는다. 이제 마지막으로 복잡도 분석을 하자. 

각 단계에서 가장 핵심적인 비용은 역시 $\phi(n)$의 계산이다. 에라토스테네스의 체 등을 사용하지 않았다고 가정하면, $\phi(n)$의 계산은 $n$의 소인수분해가 필요하며 이는 $\mathcal{O}(\sqrt{n})$에 할 수 있다. 최대 $\mathcal{O}(\log n)$ 번의 단계가 필요하므로, 전체 시간복잡도는 $\mathcal{O}(\sqrt{n} \log n)$이다. 끝.

관련 코드는 github에서 찾아볼 수 있다.

이 주제도 이미 좋은 자료가 있습니다. https://casterian.net/archives/609

사실 3단원까지만 잘 이해해도 CP/PS 하는데는 문제가 없습니다. 레드까지는 문제 없을듯 ㅋㅋ 

소개가 늦었지만, 앞서 다룬 $ax \equiv b \pmod{c}$와 같이 mod 연산을 다루는 방정식을 합동식이라 한다.

중국인의 나머지 정리는 자연수 $a_1, n_1, a_2, n_2, \cdots , a_k , n_k$가 주어졌을 때, 연립합동식 $$ x \equiv a_i \pmod{n_i} \quad i = 1, 2, \cdots k $$를 푸는 알고리즘이다. 우리의 첫 목표는 $k=2$인 경우를 푸는 것이다. 나중에 가면 알겠지만, $k=2$만 풀면 끝이다.

$x \equiv a_1 \pmod{n_1}$, $x \equiv a_2 \pmod{n_2}$가 성립한다고 가정하자. 정의상, $x = n_1 y + a_1$인 정수 $y$가 있다.

그러니 우리는 $n_1y + a_1 \equiv a_2 \pmod{n_2}$, 또는 $n_1 y \equiv a_2 - a_1 \pmod{n_2}$를 풀면 된다.

그런데 이러한 형태의 합동식은 이미 푸는 방법을 알고 있다. 바로 앞에서 배웠기 때문.

• $g = \text{gcd}(n_1, n_2)$라 하자. 만약 $a_2-a_1$이 $g$의 배수가 아니라면 해는 존재하지 않는다.
• 만약 $a_1 \equiv a_2 \pmod{g}$라면, 앞선 결과에서 우리는 $y \equiv t \pmod{n_2/g}$ 형태의 결과를 얻는다.
• 이는 다른 말로, 적당한 자연수 $m$이 있어서 $y = (n_2/g) m  + t$이라는 것이다.
• $x = n_1y + a_1$에 그대로 대입하면, $x = (n_1n_2/g) m + (n_1t+ a_1)$이다. 즉, $x \equiv (n_1t+ a_1) \pmod{n_1n_2/g}$.
• 여기서 $n_1n_2 / g$가 $\text{lcm}(n_1, n_2)$임을 확인하자. $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$라는 결과 때문.

결국 $k=2$일 때의 결론은, 연립합동식이 해가 없거나 아니면 $x \equiv \text{something} \pmod{\text{lcm}(n_1, n_2)}$라는 결론을 얻는다는 것이다.

이는 연립합동식의 해가 존재하는 경우, 두 합동식을 하나의 합동식으로 합칠 수 있다는 의미가 된다.

• Example. $x \equiv 17 \pmod{42}$, $x \equiv 23 \pmod{60}$을 풀어보자.
• $x \equiv 17 \pmod{42}$에서, $x = 42m + 17$이라고 쓸 수 있다. 
• 이제 $42m + 17 \equiv 23 \pmod{60}$을 풀자. 이는 $42m \equiv 6 \pmod{60}$을 푸는 것과 같다.
• 앞에서 배운 방식을 생각하면, $42m+60n = 6$을 풀면 된다. $\text{gcd}(42, 60) = 6$이므로, $6$으로 식을 나누자.
• $7m+10n = 1$을 풀자. 이는 확장 유클리드 알고리즘으로 가능하며, $m=3$, $n=-2$를 얻는다.
• 여기서 우리는 $m \equiv 3 \pmod{10}$을 얻는다. $m=10t+3$이라 쓰고, $x=42m+17$에 대입하자.
• 그러면 $x = 42(10t+3)+17 = 420t + 143$을 얻고, 이는 $x \equiv 143 \pmod{420}$을 의미한다. 

이제 $k \ge 3$인 경우도 간단하게 해결할 수 있다. 두 합동식을 하나의 합동식으로 합치는 것을 반복하기만 하면 된다.

만약 중간 과정에서 "해가 없다"라는 결론이 나온다면, 전체 연립합동식 역시 해가 없다는 것을 바로 파악할 수 있다.

중국인의 나머지 정리, Chinese Remainder Theorem을 줄여서 CRT로 많이 부른다. 

중국인의 나머지 정리의 심화/응용 내용으로 Garner's Algorithm이 있다. CRT로 큰 수를 다루는 방법이다. 관심이 있다면 링크 참조.

관련 코드는 github에서 찾아볼 수 있다.

이 주제는 이미 좋은 자료가 있습니다. https://casterian.net/archives/601

이 글은 유클리드 알고리즘은 이미 어느 정도 숙지한 독자를 위해 작성하였다. 유클리드 알고리즘 관련 자료 역시 많다.

글의 핵심 목적은 유클리드 알고리즘의 핵심 아이디어 2개를 짚고, 확장 유클리드 알고리즘도 사실 별반 다를 거 없다는 것을 주장하는 것이다.

앞쪽 내용인만큼 제대로 이해해야 뒤 내용을 이해할 수 있으니, 시간을 많이 투자해보자. 

유클리드 알고리즘은 자연수 $a, b$가 주어졌을 때, $\text{gcd}(a, b)$를 구하는 방법이다. 결국 핵심 아이디어는

• 아이디어 1. 몫, 나머지를 구하여 $a = bq + r$로 쓰자. 이때 $\text{gcd}(a, b) = \text{gcd}(b, r)$이다. 
• Why? $g|a$, $g|b$가 성립한다고 가정하면 $g|(a-bq)=r$이므로, $g|b$, $g|r$.
• 반대로 $g|b$, $g|r$이 성립한다고 가정하면 $g|(bq+r)=a$이므로, $g|a$, $g|b$. 
• 즉, $g$가 $a, b$의 공약수인 것과 $g$가 $b, r$의 공약수인 것은 완전히 동치이다. 그러니 최대공약수 역시 동일.

• 아이디어 2. 위 사실은 문제를 $(a, b)$에서 $(b, r)$로 "축소"하는 방법을 제시해준다. 즉, $\text{gcd}(a, b)$를 구하는 문제를 $\text{gcd}(b, r)$을 구하는 문제로 축소.
• 얼마나 줄어들까? $a \ge b$를 가정하자. 그러면 $q \ge 1$이며 $2r \le (q+1)r = rq + r \le bq + r = a$이므로 $2r \le a$.
• 그러므로, $br \le (1/2) ab$임을 얻는다. 즉, 문제를 정의하는 두 인자의 곱이 적어도 반 이상은 감소한다.

두 아이디어를 합치면, 로그 시간을 거쳐서 최대공약수를 얻는 방법이 완성된다.

$(a, b)$를 $(b, r)$로 변환하는 과정을 거치면, 로그 시간 이내에 $(g, 0)$ 형태의 순서쌍을 얻는 것이 보장되기 때문이다.

이 시점에서 $\text{gcd}(a, b) = g$를 얻고, 알고리즘을 종료시키면 된다. 여기서부터는 구현의 문제다.

• Example. $\text{gcd}(576, 204)$를 구한다고 가정하자. 다음 과정을 거친다.
• $576 = 204 \times 2 + 168$이므로, $(576, 204)$에서 $(204, 168)$로 문제를 축소
• $204 = 168 \times 1 + 36$이므로, $(204, 168)$에서 $(168, 36)$으로 문제를 축소
• $168 = 36 \times 4 + 24$이므로, $(168, 36)$에서 $(36, 24)$로 문제를 축소
• $36 = 24 \times 1 + 12$이므로, $(36, 24)$에서 $(24, 12)$로 문제를 축소
• $24 = 12 \times 2 + 0$이므로, $(24, 12)$에서 $(12, 0)$으로 문제를 축소. 답은 이제 $12$. 

아이디어 1, 2는 CP/PS의 많은 정수론 문제에서 사용되는 아이디어다. 이를 유클리드 알고리즘의 활용에서 다룬다.

확장 유클리드 알고리즘은 자연수 $a, n$이 주어졌고 $\text{gcd}(a, n) = 1$일 때, $ax \equiv 1 \pmod{n}$인 $x$를 찾는 알고리즘이다.

(엄밀하게 말하자면, 자연수 $a, b$에 대하여 $ax + by = \text{gcd}(a, b)$인 $x, y$를 찾는 알고리즘이다. 사실상 똑같은 말)

이 문제를 바라보는 가장 정석적인 방법은 변수를 하나 추가하는 것이다.

• $ax \equiv 1 \pmod{n}$이라는 것은, 정수 $y$가 있어 $ax + ny = 1$이라는 것과 동치이다.
• 그러니 사실 우리는 $ax + ny = 1$을 만족하는 정수 순서쌍 $(x, y)$를 찾으면 된다. 
• 여기서 우리가 $\text{gcd}(a, n) = 1$이라는 조건을 추가한 이유도 알 수 있다. 위 식의 좌변이 무조건 $\text{gcd}(a, n)$의 배수이기 때문.

목표는 이제 $\text{gcd}(a, b) = 1$을 가정하고 $ax + by = 1$을 푸는 것이다. 문제를 바라보는 새로운 시각을 얻었으니, 위 아이디어 1, 2를 적용해보자.

• 아이디어 1. 몫, 나머지를 구하여 $a = bq+r$로 쓰자. $a, b$에 대한 문제를 $b, r$에 대한 문제로 바꿀 수 있는가?
• 가능하다. $ax + by = 1$은 $(bq+r)x + by = 1$과 동치이며, 정리하면 $b(qx+y) + rx = 1$로 쓸 수 있다.
• 그러니, $bx'+ry'=1$인 정수 순서쌍 $(x', y')$을 구하면, $qx + y = x'$, $x = y'$을 풀어 $ax + by = 1$인 $(x, y)$를 얻는다.
• 위 식을 다시 정리하면, 결국 $x = y'$, $y = x' - qy'$이므로, 이 순서쌍 $(x, y)$는 정수 순서쌍이다. 
• 이는 $(b, r)$에 대한 문제를 풀면, 빠르게 $(a, b)$에 대한 문제를 풀 수 있음을 의미한다.

• 아이디어 2. 역시 아이디어 1은 문제 축소의 의미를 담는다. 기존 유클리드 알고리즘에서 한 논의가 그대로 성립한다.
• 결과적으로, 위 과정을 로그번 거치면 결국 $(1, 0)$에 대한 문제를 해결하는 것으로 문제가 환원된다. 이는 $x=1, y=0$이라는 해가 있다.

두 아이디어를 합치면, 로그 시간을 거쳐서 조건을 만족하는 $x$를 찾을 수 있다. 이를 modular inverse라고 부르며, 이는 유일하게 존재한다.

알고리즘을 설명하는 과정에서 $ax + by = 1$을 만족하는 정수 순서쌍 $(x, y)$가 존재함까지 증명했음을 참고하자. 

나아가면, $ax + by = \text{gcd}(a, b)$인 $x, y$가 존재함을 얻는다. 이를 Bezout's Identity라고 한다.

• Example. $3x \equiv 1 \pmod{7}$을 만족하는 $x$를 구해보자.
• $3x + 7y = 1$인 정수 순서쌍 $(x, y)$를 찾으면 충분하다. 
• 이는 $3(x+2y) + y = 1$과 같다. 그러니 이제 $3a + b = 1$인 정수 순서쌍 $(a, b)$를 찾자.
• 이는 $1(3a+b) + 0a = 1$과 같다. 이제 $3a + b = 1$, $a = 0$을 풀어 $a = 0, b = 1$을 얻는다.
• 다시 위로 돌아가서, $3(x+2y) + y = 1$을 $3a + b = 1$로 변환한 것을 생각해보자.
• 우리의 목표는 이제 $x + 2y = 0$, $y=1$. 이를 풀면 $x= -2$와 $y = 1$을 얻는다.
• 실제로 $3(-2) \equiv 1 \pmod{7}$임을 쉽게 확인할 수 있다.

• $ax+by=1$이면, 각 정수 $t$에 대하여 $a(x+bt) + b(y-at) = 1$이 성립한다. 즉 $(x+bt, y-at)$ 역시 해.
• $t$를 잘 잡아서, $x+bt$가 $0$ 이상 $b$ 미만이 되도록 할 수 있다. overflow 방지를 위해 필요한 작업이다.
• 즉, 해를 재귀적으로 계산하는 과정에서, 해가 지나치게 크거나 작아지지 않도록 하는 과정이 필수적이다. 
• 위 Example을 보면 느낌이 오겠지만, 이 알고리즘은 재귀적으로 작성하는 것이 정신건강에 좋다.

더 나아가면, 아무런 가정 없이도 $ax \equiv b \pmod{n}$과 같은 식을 해결할 수 있다.

• 마찬가지 아이디어로, $ax + ny = b$라는 식을 해결하는 것으로 문제를 바꾸자.
• $g = \text{gcd}(a, n)$을 유클리드 알고리즘으로 구하자. 위 식의 좌변 $ax+ny$는 무조건 $g$의 배수임을 알 수 있다.
• 그러니, $b$가 $g$의 배수가 아니라면 해가 없음을 바로 알 수 있다. 
• 이제 $g|b$를 가정하고, 식을 $(a/g)x + (n/g)y = (b/g)$로 써보자. 이제 $\text{gcd}(a/g, n/g) = 1$이다.
• 확장 유클리드 알고리즘으로, $(a/g)x' + (n/g)y' = 1$인 정수 순서쌍 $(x', y')$을 찾을 수 있다.
• 이제 $x = (b/g)x'$, $y = (b/g) y'$을 선택하면 $ax + ny = b$임을 알 수 있다.
• 또한, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$ 역시 각 정수 $t$에 대하여 해임을 알 수 있다.
• 즉, $x \equiv \text{something} \pmod{n/g}$ 형태의 해를 얻는다. 자세한 디테일은 github 참고.

• Example. $12x \equiv 18 \pmod{54}$를 해결해보자.
• $12x + 54y = 18$을 해결하면 충분하다. $\text{gcd}(12, 54) = 6$임을 유클리드 알고리즘으로 계산한다.
• $18$은 $6$의 배수이니, 해가 존재한다. 식을 $6$으로 나누어주자. $2x + 9y = 3$을 얻을 수 있다.
• 이제 $\text{gcd}(2, 9) = 1$이니, $2x' + 9y' = 1$인 $x', y'$를 확장 유클리드 알고리즘으로 찾을 수 있다.
• $x'=5$, $y'=-1$을 찾았다고 하자. 이제 이 값을 $3$배 해주면 $x = 15$, $y = -3$을 얻는다.
• 이제 $x \equiv 15 \pmod{9}$, 또는 $x \equiv 6 \pmod{9}$가 답이 된다. 끝!  

사실 위 논의에서 일부 엄밀한 수학적 논의를 생략했다. 내용을 추가할 겸 간략하게 설명한다.

• 우리는 이미 확장 유클리드 알고리즘으로 $\text{gcd}(x, y) = 1$이면 $ax+by=1$인 정수 $a, b$가 존재함을 안다. (엄밀하게 증명한 것은 아니나, 나름 합리적으로 유도했다. "수학자들의 증명"을 원하면 당연히 정수론 책 참고.) 이를 통해 $\text{gcd}(a, b)=1$, $a|c$, $b|c$가 성립하면 $ab|c$가 성립함도 증명할 수 있다. 또한, $a|bc$이고 $\text{gcd}(a,b)=1$이면 $a|c$가 성립함도 증명할 수 있다. 특히, $g=\text{gcd}(a, b)$라면 $\text{gcd}(a/g, b/g)=1$이니 $a|bc$에서 $(a/g)|(b/g)c$를 얻고, 즉 $(a/g)|c$임 역시 얻을 수 있다. 즉, $a/\text{gcd}(a,b)$가 $c$의 약수가 되어야 한다. 이 "증명할 수 있다"라는 부분을 자세히 알고 싶다면 정수론 책 참고 or 댓글로 질문. 이 정도 내용은 알아야 정수론 문제 해결에 지장이 없을 것이라고 생각하여 추가한다.

• modular inverse는 유일한가? $x, y$가 모두 $\pmod{n}$에 대한 $a$의 modular inverse라고 하자. 그러면 가정 상 $\text{gcd}(a, n)=1$이고 $n|(ax-1)$, $n|(ay-1)$이니 두 식을 빼면 $n|a(x-y)$를 얻는다. 한편, $a|bc$이고 $\text{gcd}(a, b)=1$이면 $a|c$임이 알려져 있다. 그러므로 $n|(x-y)$를 얻고 $x \equiv y \pmod{n}$이 성립한다. 즉, modular inverse는 ($n$으로 나눈 나머지를 보았을 때) 유일함을 얻는다. 증명 끝.
• $ax \equiv b \pmod{n}$의 해는 정말 저게 다인가? $ax+ny=b$를 생각할 때, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$가 해임은 직접 대입을 통해서 자명하게 얻을 수 있다. 이것들만이 해라는 것 역시 보여야 한다. 만약 $ax+ny = ax'+ny'=b$라면, $a(x-x')=n(y'-y)$가 된다. 여기서 $x-x'$이 $n/g$의 배수, $y-y'$이 $a/g$의 배수임을 증명할 수 있다. 즉, 해가 되려면 $(x + n/g \cdot t, y - a/g \cdot t)$ 형태를 가져야 한다. 증명 끝.

관련 코드는 github에서 찾아볼 수 있다.

여기서는 잘 알려진 사실들부터 시작해서, 나중에 중요해질 수학적 사실들을 다룬다.

사실 1단원과 2단원 앞 유클리드 알고리즘만 알아도 퍼플/오렌지에 영향은 없다.

잘 알려진 사실들은, 매우 간단하게만 설명하고 스킵하자. 이미 좋은 자료/블로그가 많으니, 이를 참고하는 것 추천.

다음 사실은 유명하다 : 정수 $a, b$가 있고 $b \neq 0$일 때, $a = bq + r$이고 $0 \le r < |b|$인 정수 $q, r$이 유일하게 존재한다.

이때, $r$을 "$a$를 $b$로 나눈 나머지"라고 정의한다. 만약 $r = 0$인 경우, $a, b$는 서로 약수/배수 관계에 있다고 하며, $b|a$라 쓴다.

이를 통해서 공약수/공배수 개념을 정의할 수 있으며, 나아가 최대공약수/최소공배수의 개념을 정의할 수 있다.

자연수 $n \ge 2$가 각 $2 \le k < n$에 대하여 $k \nmid n$을 만족하면, $n$을 소수라고 부른다. 소수가 아니면 (1 제외) 합성수라고 부른다. 

이를 통해서 소인수분해라는 개념을 정의할 수 있으며, 이는 유일하다는 것이 잘 알려져 있다.

소인수분해를 통해서, 자연수의 약수의 개수와 약수들의 합 등을 계산할 수 있음은 교육과정에도 있는 내용이다.

만약 두 정수 $a, b$가 $n$으로 나눈 나머지가 같다면, $a \equiv b \pmod{n}$이라고 쓴다. 이는 $n|(a-b)$와 같은 뜻이다.

또한, $a$를 $n$으로 나눈 나머지를 $a \pmod{n}$이라고 쓰기도 한다. 다음은 간단 Exercise.

• 정수 $a, b, n$이 $a \equiv b \pmod{n}$이고, $r$이 정수인 경우, 다음이 모두 성립함을 보여라.
• $a + r \equiv b+ r \pmod{n}$, $a - r \equiv b - r \pmod{n}$, $ar \equiv br \pmod{n}$.

즉, mod 연산을 취하는 과정에서도 평소처럼 사칙연산을 할 수 있다. 

나눗셈이 문제인데, 다음 단원에서 modular inverse가 나오면 나눗셈도 modular inverse를 양변에 곱하는 방식으로 할 수 있다.

이 시점에서, 알고리즘 문제를 몇 개 생각해볼 수 있다. 모두 이미 자료가 많으므로, 빠르고 간단하게 한다.

• 자연수가 소수임을 어떻게 판별할 것인가?
• 자연수의 약수의 개수를 어떻게 셀 것인가? 약수를 모두 찾으라고 한다면 어떻게 할 것인가?
• 자연수의 소인수분해를 어떻게 구할 것인가?
• 1부터 $n$까지의 소수를 어떻게 셀 것인가/찾을 것인가?

첫 세 문제에 대해서는, $\mathcal{O}(\sqrt{n})$ 알고리즘이 잘 알려져 있다. 핵심 아이디어는,

• 자연수 $n$이 $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 의해 나누어떨어지지 않는다면, $n$은 소수다.
• 이유: 소수가 아니라면 $n = ab$이며 $1  < a , b < n$인 자연수 $a, b$ 존재. 둘 다 $\sqrt{n}$보다 크다면 $ab > n$.

이 핵심 아이디어로 세 문제를 해결해보자.

• 소수 판별: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 대해 나누어떨어짐을 판별하면 끝.
• 약수 세기/찾기: $a$가 $n$의 약수면 $n/a$ 역시 $n$의 약수. 둘 중 하나는 $\sqrt{n}$ 이하고 하나는 $\sqrt{n}$ 이상이니, $\sqrt{n}$ 이하 약수만 찾으면 모든 약수를 알 수 있다.
• 소인수분해: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수를 순서대로 보자. 현재 보고 있는 자연수 $i$가 $n$의 약수라면, $n$이 $i$의 배수가 아닐 때까지 $n$에서 $i$를 나누어준다. 나누어주는 횟수를 저장하는 것은 당연. 만약 iteration이 끝났을 때, $n$이 $1$이면 그대로 끝. 아니면 남은 $n$ 역시 소수이며, 기존 $n$의 소인수가 된다. 

마지막 문제는 "에라토스테네스의 체"로 잘 알려져 있는 결과다.

• 에라토스테네스의 체: 2부터 $n$까지 순서대로 보면서, 합성수인 것을 지워내자. 만약 지금 보는 값 $p$가 지워지지 않았다면, $p$는 소수다. 
• 이제 $p$의 배수를 ($p$는 빼고) 전부 지워내자. 이걸 반복하면 남는 것은 전부 소수. 예시를 인터넷에서 찾아보면서 이해해보자. 

에라토스테네스의 체는 활용 방법이 굉장히 많다. 다음을 할 수 있는 방법을 생각해보자. 해답은 github에 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 계산하는 법
• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 서로 다른 소인수 개수"를 계산하는 법
• 오일러 파이 함수. $n$의 소인수분해가 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$일 때, $\phi(n) = n \cdot \frac{p_1 - 1}{p_1} \cdots \frac{p_k-1}{p_k}$라 정의하자. 이 값을 모두 계산하는 법.
• 조금 더 난이도가 있지만, "약수의 개수"와 "약수의 배수" 역시 전처리 할 수 있다.

여기서 강력한 결과를 하나 얻을 수 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 미리 전처리했다고 가정하자.
• 이제 $2 \le m \le n$인 자연수 $m$의 소인수분해를 원한다고 가정하자. 
• $m$에서 시작해서, "가장 작은 소인수"를 나누어주는 과정을 반복하자. 한 번에 값이 반 이상 줄어드니, 로그 시간에 소인수분해 끝.

에라토스테네스의 체를 사용하면 $1, 2, \cdots , n$ 각각이 소수인지 전부 빠르게 판별할 수 있다.

하지만 꼭 $1$부터 시작할 필요는 없다. $A+1, A+2, \cdots , A+n$ 각각이 소수인지 빠르게 판별할 수는 없을까?

• $2$부터 $\sqrt{A+n}$까지의 수를 순서대로 보자. 현재 보고 있는 수를 $k$라고 하자.
• $A+1, A+2, \cdots , A+n$에 속한 $k$의 배수 중 $k$가 아닌 것을 전부 제거하자. 남는 것은 전부 소수이다.
• 시간복잡도는 어떻게 될까? 각 $k$에 대하여 제거되는 수의 개수는 $\mathcal{O}(n/k)$개이다.
• 이를 $k$를 $2$부터 $\sqrt{A+n}$까지 돌면서 더하면, 아래에서 다룰 Harmonic Sequence에 대한 성질에 의해 총 $\mathcal{O}(n \log n)$이 된다.
• 그러니 $k$에 대하여 for문을 돌리기 위해 필요한 시간 $\mathcal{O}(\sqrt{A+n})$을 더하면, $\mathcal{O}(\sqrt{A} + n \log n)$이라는 결과를 얻는다.
• 에라토스테네스의 체의 다양한 활용 방법을 이 방식에서도 그대로 적용할 수 있다.

참고할 점은, 위의 에라토스테네스의 체가 하는 일을 $\mathcal{O}(n)$에 하는 방법이 존재한다는 것이다.

• Linear Sieve라고 하는 테크닉이다. 이를 위해서는 ahgus89님의 이 자료나, 원본이라고 할 수 있는 이 글을 보자.
• 이후에 다룰 multiplicative function에 대한 글을 읽고 다시 위의 자료를 읽는 것이 이해하기 편할 수 있다.
• 이 가이드에서 굳이 Linear Sieve를 설명하지 않는 이유는, 필자도 Linear Sieve가 필요할 정도로 시간제한이 빡빡한 문제를 본 적이 없기 때문이다.
• 이 외에도, 에라토스테네스의 체는 다양한 최적화 방법이 있다. 개인적으로는 필요한 문제를 본 적이 없었다. 필요하면 나쁜 문제라는 것이 내 생각.
• 당연하지만, 이러한 체 최적화 방법을 알아둬서/팀노트에 넣어서 나쁠 것은 없다. 나중에 관심이 생기면 보는 것으로.

이제 여러 수학적 사실들을 빠르게 다룬다. 중요해지는 때가 온다.

• [매우 중요] 자연수 $n$에 대하여, $\lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \cdots, \lfloor n/n \rfloor$ 중 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개이며, 효율적인 iteration도 가능. github 참조.
• 이유가 꽤 아름다우니 설명한다. $\lfloor n/1 \rfloor, \cdots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor$까지 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개. (항 개수가 애초에 $\mathcal{O}(\sqrt{n})$개이므로)
• $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \cdots ,\lfloor n/n \rfloor$까지 서로 다른 것도 $\mathcal{O}(\sqrt{n})$개. (값들이 전부 $\mathcal{O}(\sqrt{n})$ 이하이므로)
• 위 github 코드의 iteration 방법의 원리가 궁금할 수 있을 것이다. 이것의 대한 설명은 ahgus89님의 이 글 참고.
• [매우 중요] Harmonic Sequence. 자연수 $n$에 대하여, $1/1 + 1/2 + 1/3 + \cdots + 1/n = \mathcal{O}(\log n)$.
• 7단원에서 언급하겠지만, 이를 통해서 $1$부터 $n$까지 약수의 개수 합이 $\mathcal{O}(n \log n)$임을 얻는다.
• 그러므로, 만약 필요하다면, $1$부터 $n$이 갖는 약수들을 std::vector 등 자료구조에 $\mathcal{O}(n \log n)$ 시간에 넣을 수 있다.
• 더욱 자세한 내용을 알고 싶다면, 7단원에서 "약수를 iterate 하는 것보다 배수를 iterate 하는 것이 쉽다"는 부분을 읽자.
• Merten's 2nd Theorem. 자연수 $n$에 대하여, $n$ 이하 소수들의 역수의 합은 $\mathcal{O}(\log \log n)$.
• Merten's 2nd Theorem으로, 에라토스테네스의 체의 시간복잡도를 파악할 수 있을 것이다. $\mathcal{O}( n \log \log n)$.
• 후반부의 내용에서, 은근슬쩍 자연수 $a, b, c$에 대하여 $\lfloor \lfloor a/b \rfloor / c \rfloor = \lfloor a/(bc) \rfloor$라는 식을 꽤 사용한다.

마지막으로, 모듈로 연산에 대해 잠깐 언급한다. 이 연산은 덧셈, 뺄셈에 비해서는 물론, 곱셈에 비해서도 느린 연산이다.

그러니, 모듈로 연산을 마구잡이로 사용하면 비효율적인 코드가 나오게 될 것이다. 이를 최적화하는 방법을 간단히 소개한다.

모듈로 연산 횟수를 줄이는 법

• 가능하면 진짜 나머지를 취하지 말고, 모듈러스를 더하고 빼는 것으로 대체한다.
• 예를 들어, $0 \le a < M$, $0 \le b < M$에 대해, $a+b \pmod{M}$을 계산하기 위해서 모듈로 연산을 쓰지 말자는 것이다.
• $a+b$를 계산한 다음, $M$보다 큰 경우 $M$을 빼는 것이 훨씬 효율적이다. 쉽고 확실한 최적화 방법이다.

모듈로 연산 자체를 빠르게 하는 방법

• 모듈로를 가능하면 const로 선언하자. 그러면 상당한 속도 개선을 확인할 수 있다.
• 이러한 고속화의 원리 중 하나는 Barrett Reduction이다. modulo 연산을 곱셈과 시프트 연산으로 대체한다.
• 자세한 내용을 알고 싶다면, 이 위키피디아 글과 이 min_25의 글을 확인하라.
• 어셈블리를 잘 아는 사람이라면 어셈블리를 이용할 수 있는 것으로 안다. 이 부분은 내가 모르니 생략. 이 링크를 보자.
• 관련 내용이 KAIST의 ICPC팀이었던 더불어민규당의 팀노트에도 있다. Fast LL Division/Modulo 부분을 보자.

PS를 위한 정수론 가이드를 쓰기로 했다. 이유는 여러 가지.

• 자료가 부족하다는 의견을 많이 듣고, 동의함
• kipa00님의 NTA가 매우 좋은 자료인 것은 맞지만, 진입장벽이 상당하다
• 수학적 직관이나 엄밀한 증명을 일부 포기하더라도 내용을 간결하게 전달하는 것이 필요한 것 같다
• (나중에 직관/증명이 필요하다면, 그 때 직접 자료를 찾으면 된다. 처음 들이박는 것보다 쉬울 것)
• 그래서 최대한 문제 풀이에 집중하는 가이드가 필요하다고 생각했다
• 그러나, 각 알고리즘의 기본 원리 정도는 배우고 갈 수 있도록 내용을 작성하였다.
• (목표는 PS 정수론을 입문하기 위해 책을 폈다가 수학적 귀납법부터 시작하면서 의지를 잃는 사람들을 배려하는 것) 

이론 설명은 여기에 간단하게 하고, 관련 코드를 github에 올릴 계획. git 연습도 해야하니. 

연습문제도 올릴 예정인데, 이건 천천히 할 생각이다. 초반 주제들은 solved.ac에 관련 태그가 많으니 활용하자.

글을 읽다보면 뭔가 논리에 빈 공간이 있다는 생각이 들 수도 있다. 정수론 책을 그대로 옮기고 싶지 않아서 그런 것이다.

논리의 허점에 아쉬움을 느끼는 때가 오면, 학부용 정수론 책을 사서 읽으면 도움이 될 것이다. 위에서도 말했지만..

(+ 당연한거지만 학부 정수론을 모르는 상태로 어려운 문제를 풀려고 하면 한계가 올 것이다. 그때 필요하면 책을 읽으면 된다. 앞 몇 장만 읽어도 도움된다.)

일단 내용을 최대한 빠르게 퀄리티 신경 안 쓰면서 뽑아내고, 지적이나 제안을 받아가면서 천천히 보완할 생각이다. 

한 번에 완벽한 자료를 만들려고 하면 한 3~4단원하고 접을 가능성이 99.9%라서인데 사실 이게 더 나을수도 ㅋㅋㅋㅋ

가끔 오개념을 글에 쓰고 난 다음 나중에 고치는 일이 생길 수 있어, 글이 올라온 뒤 조금 시간이 지난 다음 읽는 것을 추천한다.

추가적으로 해야하는 언급들

• 시간복잡도 분석은 빡빡하게 하지 않을 것이다. 본격적으로 시간복잡도를 논의하려면 정수 덧셈도 로그 시간이라는 내용들을 녹여내야한다. 하지만 PS/CP에서 이렇게 시간복잡도를 분석하는 경우는 흔치 않으니, 여기서도 모든 덧셈과 곱셈은 $\mathcal{O}(1)$ 연산이라는 것으로 합의하자. 
• 비슷하게, $\mathcal{O}$ notation도 꽤 편안하게 (엄밀하지 않게) 사용할 것이다. 적당히 이해하고 넘어가자 :)
• 자료 수정/추가는 가끔 오류가 보이거나 필요가 생기면 할 것이다. github에서도 수정이 많을 수 있다.
• github에 올라온 코드는 팀노트에 복붙해서 넣을 퀄리티가 아니라, proof of concept 정도로 보는 것이 나을 것이다.

solved.ac 기준. 1~3 및 5 초반은 플레 중하위권 이하, 4, 5 후반은 플레 중상위권, 6번은 플레, 7, 8은 플레 상위권, 9~11번은 다이아 이상.

예상 커리큘럼

1. 기본기 잡기
2. 유클리드, 확장 유클리드 알고리즘
3. 중국인의 나머지 정리
4. 페르마 소정리, 오일러 정리 및 활용
5. 팩토리얼과 이항계수
6. Miller-Rabin 소수 판별 알고리즘과 Pollard-Rho 소인수분해
7. Mobius function과 그 활용
8. 원시근, 이산로그, 이산제곱근
9. 유클리드 알고리즘의 활용
10. 소수의 개수 빠르게 세기
11. more on multiplicative functions
12. 개인적인 후기, 그리고 그 이후의 이야기

1단원은 이미 자료가 많은 부분을 다루어, 덜 친절할 예정이다. 이 부분은 다른 자료를 찾는 것을 추천한다.

UPD: 백준 문제집 - 6593번 ~ 6603번

질문은 댓글로 항상 환영 :) (나도 내가 설명을 쉽게 못하는 사람인 걸 안다)