개요

이 포스팅에서는 PS를 하는데 필요한 기초적인 정수론 내용에 대하여 다룬다.

소수 판별법과 소인수 분해

1개의 소수 판별

소수를 판별하는 가장 간단한 방법은 $1 \sim n$ 까지 모든 수로 나눠보는 것이다. 하지만 실제로는 $1\cdots{}\sqrt{n}$ 까지만 조사해도 충분한데, 그 이유는 $n=ab\ (a\leq b)$ 라고 할 때, $\sqrt{n} < a$ 인 경우 $a\leq b$ 가 성립하지 않기 때문이다. 따라서 일반적인 문제에서 어떤 수가 소수인지 판별하고, 이를 소인수 분해할 경우 $O(\sqrt{n})$ 에 이를 해결할 수 있다. 참고로 더 빠른 소수 판별 알고리즘과 소인수 분해 알고리즘이 존재하며 간혹 출제가 되는 경우도 있으니 팀노트에 넣는 것도 괜찮은 선택이다. (밀러-라빈 소수 판별법, 폴라드 로 알고리즘)

$[1,n]$ 중 소수 판별

이 경우는 위의 방식을 적용하지 않고, 에라토스테네스의 체라고 하는 방식을 적용한다. 2부터 $n$ 까지 숫자를 차례로 보면서, 소수인 경우 그 수들의 배수를 지우는 형식으로 이루어진다. 앞서 첫번째 포스팅에서 다룬 내용과 이 글의 마지막 사실로부터 시간 복잡도가 $O(n\log{\log{n} })$ 임을 알 수 있다. (사실상 거의 선형시간에 가깝지만, 실제 선형시간에 구현을 하는 방법도 존재하며 Linear-sieve 라고 검색하면 알 수 있다.)

최대 공약수와 유클리드 호제법

최대 공약수는 말 그대로 어떤 두 수의 공약수 중 가장 큰 수를 말한다. 흔히 $\gcd(a,b)$ 와 같이 표기하며, 이를 구하는 효율적인 알고리즘은 유클리드 호제법이다. 유클리드 호제법은 $\gcd(a,b)=\gcd(b,r)\ (a=bq+r, 0\leq{r} < b)$ 이 성립한다는 사실로부터 최대 공약수를 빠르게 구할 수 있게 해준다. 유클리드 호제법의 시간 복잡도는 $O(\log{(a+b)})$ 이다. (참고로 algorithm 헤더의 std::__gcd 함수를 이용하면 편하다.)

서로소와 오일러 $\phi$ 함수

서로소는 최대 공약수가 1인 두 수의 관계를 의미한다. 예를 들어 $d=\gcd(a,b)$, $a\over{d}$ 와 $b\over{d}$ 는 서로소 관계이다. 최대 공약수가 1인 쌍을 서로소라고 부른다는 정의를 이용하여, 유클리드 호제법을 사용하면 두 수의 관계를 파악할 수 있다. 하지만 어떤 수 $n$ 과 서로소인 모든 수들의 개수가 궁금한 경우는 어떻게 해야할까? 이 경우는 오일러 $\phi$ 함수를 사용하면 된다. 오일러 $\phi$ 함수는 어떤 수 $n$ 과 서로소인 모든 수들의 개수를 구해주는 함수로써 다음과 같이 정의된다.

$n={p_1}^{e_1}{p_2}^{e_2}\cdots{}{p_k}^{e_k}$ 라고 할 때,
\[\displaystyle \phi(n)=n\prod_{i=1}^k (1-{1\over{p_i} })=\prod_{i=1}^k ({p_i}^{e_i}-{p_i}^{e_i-1})\]

위의 식을 보면 알겠지만, $n$을 소인수 분해한 결과물이 필요함을 알 수 있다. 따라서 시간 복잡도는 소인수 분해 알고리즘의 종류에 따라 결정될 것이고 해당 글에서는 기초적인 방법만 다루므로 $O(\sqrt{n})$ 에 우리는 구하고자 하는 값을 얻을 수 있다.

합동식의 기본성질

어떤 두 수 $a$ 와 $b$가 존재한다고 하자. 이때 $m|(a-b)$ 가 성립한다면, $a$는 법 $m$에 대하여 $b$와 합동이다. 이는 수식으로 아래와 같이 표현하며, 다음과 같은 연산이 성립한다.

\[{a}\equiv{b} \pmod{m}\] \[{a+c}\equiv{b+c} \pmod{m}\] \[{a-c}\equiv{b-c} \pmod{m}\] \[{ac}\equiv{bc} \pmod{m}\]

위의 식들은 경우의 수를 구하는 DP에서 흔히 사용되는 사실이므로 꼭 기억해 놓도록 하자. 특이한 점은 합/차/곱은 성립하지만, 나누기는 성립하지 않는다는 것이다. 나누기는 제한된 조건에서만 성립하고, 이는 나중에 잉여 역수에서 다루도록 하겠다. 참고로 음수의 나머지 연산을 하면 C++에서 음수가 나오므로 a=(a-c+MOD)%MOD 와 같이 차는 구현하도록 하자.

일차합동식의 해법

일차합동식이란 ${ax}\equiv{b} \pmod{m}$ 를 만족하는 정수 $x$를 구하는 문제이다. 해당 문제는 해가 존재하는 경우가 있고, 존재하지 않는 경우가 있다. 해가 존재하기 위한 필요충분조건은 $\gcd(a,m) | b$ 이다. 또한 해가 존재한다면, 정확하게 $d$개의 서로 다른 해가 존재한다. 그렇다면 어떤 과정으로 문제를 해결하는지 알아보도록 하자.

${ax}\equiv{b} \pmod{m}$ 가 성립하므로, 이는 $ax=my’+b$ 가 성립한다는 것과 동치이다.
$y=-y’$라고 하면, $ax+my=b$ 의 정수 근을 찾는 것과 같음을 알 수 있다.
$ax+my=b$ 의 한 근을 $(x,y)=(x_0,y_0)$ 라고 하자.
주어진 일차합동식의 일반해는 다음과 같다.
임의의 $k\in{\mathbb{Z} }$ 에 대하여, $d=\gcd(a,m)$ 일때
\[x=x_{0}+{ {mk}\over{d} },\ y=y_{0}-{ {ak}\over{d} }\]
따라서 $x_{k}=x_{0}+{ {mk}\over{d} }$ 에 $k=0,1,\cdots{}, d-1$ 을 대입하여 $m$으로 나눈 나머지가 구하고자 하는 해이다.

위와 같이 일반해의 공식을 알았으니 문제가 해결된 것처럼 보이지만, 맹점이 1가지 있다. 바로 적절한 $x_{0}$ 와 $y_{0}$ 를 찾는 방법을 아직 우리는 배우지 않았다. 이 내용은 바로 뒤에 이어질 확장 유클리드 알고리즘을 이용하면 쉽게 구할 수 있다.

확장 유클리드 알고리즘

앞서 우리는 유클리드 호제법에 대하여 다루었다. 유클리드 호제법은 최대 공약수를 알려주는 알고리즘이었고, 확장 유클리드 알고리즘은 최대 공약수와 함께, $ax+by=\gcd(a,b)=d$ 를 만족하는 근을 알려준다. 아래와 같은 수식을 보고 이해를 해보도록 하자.

$\forall{i}$, ${r_{i} }\equiv{r_{i+2} }\pmod{r_{i+1} }$ 일 때,
\[{a}\cdot{1}+{b}\cdot{0}=a=r_{0}\] \[{a}\cdot{0}+{b}\cdot{1}=b=r_{1}\] \[{a}\cdot{X_2}+{b}\cdot{Y_2}=r_{2}\] \[{a}\cdot{X_3}+{b}\cdot{Y_3}=r_{3}\] \[{a}\cdot{X_4}+{b}\cdot{Y_4}=r_{4}\] \[\vdots{}\] \[{a}\cdot{X_k}+{b}\cdot{Y_k}=r_{k}=d\]

좌측 식을 제외하고, 우변의 변화만을 살펴보면 이는 일반적인 유클리드 호제법의 결과물과 같음을 알 수 있다. 그렇다면 좌변에 $ax+by$ 꼴을 얹어서 함께 계산해도 되지 않을까? 라는 아이디어로부터 확장 유클리드 알고리즘이 나온다. 따라서 아래와 같은 과정을 생각해 볼 수 있다.

$\forall{i}$, ${r_{i} }={r_{i+1}q_{i+1} }+{r_{i+2} }$ 즉, ${r_{i} }-{r_{i+1}q_{i+1} }={r_{i+2} }$
\[{a}\cdot{X_{i} }+{b}\cdot{Y_{i} }=r_{i}\ \cdots{}(1)\] \[{a}\cdot{X_{i+1} }+{b}\cdot{Y_{i+1} }=r_{i+1}\ \cdots{}(2)\] \[{a}\cdot{X_{i+2} }+{b}\cdot{Y_{i+2} }=r_{i+2}\ \cdots{}(3)\]
(2)식에 $q_{i+1}$를 곱한 결과를 (1)식에 빼면, (3)식의 결과물이 나온다.
따라서 아래와 같은 점화식이 성립한다.

$\forall{i}$, ${r_{i} }={r_{i+1}q_{i+1} }+{r_{i+2} }$
\[X_{i+2}=X_{i}-X_{i+1}\times{q_{i+1} }\] \[Y_{i+2}=Y_{i}-Y_{i+1}\times{q_{i+1} }\]

위의 과정을 이해했다면, 확장 유클리드 알고리즘을 통해 일차합동식의 특수해($X_k, Y_k$)를 구할 수 있음을 알 수 있다. 참고로 일차 부정방정식 $ax+by=c$ 의 일반해는 아래와 같음을 기억하자. (단, $x_0, y_0$는 확장 유클리드 알고리즘을 통해 얻은 $ax+by=d$의 특수해)

\[x={ {c}\over{d} }x_{0}+{ {b}\over{d} }k,\ \ y={ {c}\over{d} }y_{0}-{ {a}\over{d} }k\ \ (k\in{\mathbb{Z} ) }\]

다음은 확장 유클리드 알고리즘의 구현 코드이다.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> EEA(ll a, ll b)
{
    vector<ll> ret={1,0,a};
    vector<ll> tmp={0,1,b};
    while(tmp[2]){
        ll q=ret[2]/tmp[2];
        for(int i=0 ; i<3 ; i++) ret[i]-=q*tmp[i];
        swap(ret,tmp);
    }
    return ret;
}

오일러의 정리와 페르마 소정리

오일러의 정리와 오일러 정리의 특수 케이스인 페르마 소정리는 다음에 다룰 잉여 역수와 관련이 있다. 각각은 다음과 같다.

(오일러의 정리) $n$이 양의 정수이고, $\gcd(a,n)=1$ 이면, ${a}^{\phi(n)}\equiv{1}\pmod{n}$ 이다.
(페르마 소정리) $p$가 소수이고, $\gcd(p,a)=1$ 이면, ${a}^{p-1}\equiv{1}\pmod{p}$ 이다.

잉여 역수란 ${ax}\equiv{1}\pmod{n}$ 을 만족하는 $x$를 말한다. 곱셈에서의 역수를 곱하면 1이 되는 것처럼 모듈러 연산에 대하여 이와 같은 역할을 하는 숫자를 의미한다. 앞서 언급한 바와 같이 잉여 역수란 반드시 존재하는 것이 아닌데, 이 내용은 잉여 역수 파트에서 다루도록 하자. 오일러의 정리와 페르마 소정리를 잉여 역수와 연관지어 생각해보면 각 정리의 마지막 부분을 아래와 같이 바꾸어 생각할 필요가 있다.

(오일러의 정리) $n$이 양의 정수이고, $\gcd(a,n)=1$ 이면, ${a}{a}^{\phi(n)-1}\equiv{1}\pmod{n}$ 이다.
(페르마 소정리) $p$가 소수이고, $\gcd(p,a)=1$ 이면, ${a}{a}^{p-2}\equiv{1}\pmod{p}$ 이다.

보다시피 위와 같이 변형하면 오일러의 정리에 의해, $n$이 양의 정수이고, $\gcd(a,n)=1$ 이면, $a$의 잉여 역수는 ${a}^{\phi(n)-1}$ 이 된다. 같은 원리로 페르마 소정리에 의해, $p$가 소수이고, $\gcd(p,a)=1$ 이면, $a$의 잉여 역수는 ${a}^{p-2}$ 이 된다. 물론 이 값은 매우 크기 때문에 각각 $n$과 $p$로 나눈 나머지를 사용하면 된다.

잉여 역수

앞서 언급한 바와 같이 잉여 역수란 ${ax}\equiv{1}\pmod{n}$ 을 만족하는 $x$를 말한다. 잉여 역수가 존재하기 위한 필요충분조건은 $\gcd(a,n)=1$ 이다. 그 이유는 위에서 다룬 일차합동식의 해법을 ${ax}\equiv{1}\pmod{n}$ 에 적용한다고 생각하면 알 수있다. 잉여 역수를 구하는 방법도 1개의 숫자만을 구할 것이냐, 아니면 특정 구간의 숫자의 잉여 역수를 모두 구할 것이냐에 따라서 구현이 달라진다. 각각을 나눠서 생각해 보자. 또한 문제를 풀 때 대부분의 모듈러는 소수로 이루어지기 때문에 잉여 역수가 존재한다는 가정하에 구해보도록 하겠다.

1개의 잉여 역수를 구하는 경우

이 경우는 모듈러가 소수인 경우는 페르마 소정리를, 모듈러가 소수가 아닌 경우에는 오일러의 정리를 이용하면 된다. 앞서 다룬 내용에서 각각의 정리를 잉여 역수를 구하는데 어떻게 사용하는지 알아봤었다. 따라서 우리가 구현해야 할 핵심은 $a^{k}$을 $n$으로 나눈 나머지를 빠르게 구하는 것이다. 해당 내용은 Binary Exponentiation을 이용하여 $O(\log{k})$에 빠르게 구할 수 있다. (참고로 문제를 풀 때, 흔히 나오는 숫자들 $10^{9}+7$, $998244353$ 등은 모두 소수이다. 따라서 페르마 소정리를 이용하면 된다.)

또한 다른 방법으로 일차합동식의 해법을 ${ax}\equiv{1}\pmod{n}$ 에 적용해도 당연히 풀리며, 이때는 확장 유클리드 알고리즘을 이용하면 될 것이다.

$[1,m]$의 잉여 역수를 구하는 경우 $(m < n)$

이 경우는 DP를 이용하여 문제를 해결한다. 구현은 아래와 같고, 이후 증명을 살펴보자. 시간 복잡도는 자명히 $O(m)$ 이다.

inv[1]=1;
for(int i=2 ; i<=m ; i++){
    inv[i]=(n-(n/i)*inv[n%i])%n;
    if(inv[i]<0) inv[i]+=n;
}

Proof )
\[n\pmod{i}=n-\lfloor{ {n}\over{i} }\rfloor\cdot{i}\]
양변에 $\pmod{n}$ 을 취하면 $i < n$ 이므로,
\[n\pmod{i}\equiv{-\lfloor{ {n}\over{i} }\rfloor\cdot{i} }\pmod{n}\]
양변에 $i$와 $n\pmod{i}$의 법 $n$에 대한 잉여 역수를 각각 곱하면
\[(n\pmod{i})\cdot{i}^{-1}\cdot{(n\pmod{i})}^{-1}\equiv{-\lfloor{ {n}\over{i} }\rfloor\cdot{i}\cdot{i}^{-1}\cdot{(n\pmod{i})}^{-1} }\pmod{n}\] \[{i}^{-1}\equiv{-\lfloor{ {n}\over{i} }\rfloor\cdot{(n\pmod{i})}^{-1} }\pmod{n}\]
이는 코드에 주어진 점화식과 일치한다.

중국인의 나머지 정리(CRT)

중국인의 나머지 정리는 아래와 같은 연립 합동식을 푸는데 사용된다.

(중국인의 나머지 정리)
$m_1, m_2, \cdots{}, m_n$ 이 쌍마다 서로소(pairwise coprime) (즉, $\gcd(m_i,m_j)=1,i\ne{j}$) 이면, 다음 연립 합동식
\[{x}\equiv{a_1}\pmod{m_1}\] \[{x}\equiv{a_2}\pmod{m_2}\] \[\vdots{}\] \[{x}\equiv{a_n}\pmod{m_n}\]
은 법 ${m_1}{m_2}\cdots{}{m_n}$에 대하여 유일한 해를 갖는다.

즉, 해당 정리는 연립 합동식의 해가 유일함을 보장한다. 그렇다면 그 유일한 해는 어떻게 구할까? $\displaystyle M=\prod_{i=1}^{n}{m_i}$ 라고 할때, $x$는 아래와 같은 꼴일 것이다.

$n_k={M\over{m_k} }$ 라고 하면, $\gcd(n_k,m_k)=1$ 이므로 ${s_k}{n_k}\equiv{1}\pmod{m_k}$ 인 $s_k$ 가 존재한다.
즉, $s_k$는 ${n_k}$의 법 ${m_k}$에 대한 역원이다. 이때 아래와 같은 해 $x$를 생각해보자.
\[x\equiv{ {a_1}{n_1}{s_1}+{a_2}{n_2}{s_2}+\cdots{}+{a_k}{n_k}{s_k} }\pmod{M}\]
위 식은 $j\ne{k}$ 이면 ${n_j}$ 는, ${m_k}$ 의 배수이므로 따라서
\[x\equiv{ {a_k}{n_k}{s_k} }\equiv{ {a_k}\cdot{}1}={a_k}\pmod{m_k}\]
이다. 즉, 위의 꼴은 주어진 연립 합동식의 해이다.

이제 연립 합동식의 해가 어떻게 되는지 알았으니 어떻게 계산할지 고민해보자. 위 식의 핵심은 ${s_k}{n_k}\equiv{1}\pmod{m_k}$ 인 $s_k$ 를 찾는 것이다. 이 과정은 앞서 다룬 잉여역수를 구하는 과정에서 이미 다뤘고, 확장 유클리드 알고리즘을 이용하면 ${s_k}\pmod{m_k}$ 를 쉽게 구할 수 있다. 따라서 모든 $k$에 대하여 확장 유클리드 알고리즘을 이용하여 각각의 역원 ${s_k}\pmod{m_k}$ 을 구한 뒤, $x$를 계산하면 된다. 이때, 주의할 점은 ${a_k}{n_k}$ 의 경우, ${a_k}{n_k}\pmod{M}$ 로 계산을 하고, 전체 합을 계산할 때도, 법 $M$에 대하여 계산을 해야 한다는 것이다.

참고로 말하자면, pairwise coprime이 아닌 경우도 중국인의 나머지 정리를 이용하여 계산을 할 수가 있다. 이 경우는 추가적인 작업이 필요한데, 바로 각 숫자 $m_k$ 를 소인수 분해하여 주어진 합동식을 여러개의 pairwise coprime 한 연립 합동식으로 바꾸는 것이다. 예시 문제를 하나 제시하고 해당 문제를 푸는 과정을 이해하면, 앞서 말한 바가 무엇인지 알 것이다.

예제)
다음 연립 합동식을 풀어라.
\[x\equiv{5}\pmod{12},\ \ x\equiv{11}\pmod{18}\]
풀이)
위 식을 CRT 꼴로 바꾸도록 하자. 즉, 각각의 식을 더 작은 식으로 쪼갤 것이다.
첫번째 식은 다음과 같다. $x\equiv{1}\pmod{4}$, $x\equiv{2}\pmod{3}$
두번째 식은 다음과 같다. $x\equiv{1}\pmod{2}$, $x\equiv{2}\pmod{9}$
즉, 아래 식들을 푸는 문제와 동치이다.
\[x\equiv{1}\pmod{2}\] \[x\equiv{2}\pmod{3}\] \[x\equiv{1}\pmod{4}\] \[x\equiv{2}\pmod{9}\]
아직 위의 식은 pairwise coprime이 아니고, 따라서 법이 서로소가 아닌 식들간에 모순관계를 따져보도록 하자.
모순 관계를 따지는 방법은 각 소수별로 가장 차수가 높은 소수로 나눈 나머지를 가지고, 나머지 더 낮은 차수들로 낮춰가면서 비교를 하면 된다.
이렇게 할 때, $\pmod{4}$의 결과는 $\pmod{2}$ 와 모순이 나타나지 않고, $\pmod{9}$의 결과는 $\pmod{3}$ 과 모순이 나타나지 않으므로(=같은 법에 대하여 나머지가 다른 경우가 없음), 해가 존재하며 아래 식을 푸는 문제로 귀결된다.
\[x\equiv{1}\pmod{4}\] \[x\equiv{2}\pmod{9}\]
이제 CRT를 적용하여 문제를 풀면되고, $x$는 아래와 같다. $(9\times{s_1}\equiv{1}\pmod{4},\ 4\times{s_2}\equiv{1}\pmod{9})$
\[x\equiv{1\times{9}\times{s_1}+2\times{4}\times{s_2} }\pmod{36}\]
각각을 확장 유클리드 알고리즘을 이용하여 구하면, $s_1\equiv{1}\pmod{4}$, $s_2\equiv{7}\pmod{9}$ 이다.
따라서 $x\equiv{9+56}\equiv{29}\pmod{36}$ 이다.

풀이 과정에서 알 수 있지만, 합동식 간에 모순 관계가 존재한다면 자명히 해는 존재하지 않는다. 모순 관계가 존재하지 않으면, 가장 높은 차수의 법으로만 이루어진 pairwise coprime인 연립 합동식을 CRT를 이용하여 풀면 된다. 또한 식을 분해 한다는 것은 각 숫자를 소인수 분해한 결과물 $( n={p_1}^{e_1}{p_2}^{e_2}\cdots{}{p_k}^{e_k})$ 에서 ${p_1}^{e_1}$, ${p_2}^{e_2}$, … , ${p_k}^{e_k}$ 법으로 하는 합동식으로 나눈다는 것을 의미한다.

그 이외 사실들

$n$ 이하의 대략적인 소수의 개수 = $O\left({ n \over \log{n} } \right)$
대략적인 $n$ 번째 소수 = $O(n\log{n})$
$n$ 의 약수의 개수 $\leq 2^{\log{n}/\log{\log{n} } }$
$[1,n]$ 최대 약수 개수 = $O(n^{1/3})$