거듭제곱, 모듈러 연산, 페르마의 소정리(백준 13977)
백준 13977을 해결하기 위해서는 3가지 테크닉을 알아야한다.
- 분할정복을 이용한 거듭제곱
- 모듈러 연산 특징(for 이항계수 모듈러 연산을 위한 역원)
- 페르마의 소정리(for 이항계수 모듈러 연산)
거듭제곱
1. 일반적인 거듭제곱 : $O(n)$
일반적인 거듭제곱의 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
// 재귀함수를 이용한 거듭제곱
int pow(int a, int n) {
if(n==0) return 1;
else return a*pow(a, n-1);
}
// 반복문을 이용한 거듭제곱
int pow(int a, int n) {
int result = 1;
for(int i=1; i<=n; i++) result*=a;
return result;
}
위의 코드는 모두 시간복잡도 $O(n)$이다.
2. 분할정복을 이용한 거듭제곱 : $O(\log n)$
이를 분할정복을 이용하면 시간복잡도 $O(\log n)$으로 계산할 수 있다.
거듭제곱은 2가지 케이스로 나눌 수 있다.
- $n$이 짝수일 때 : $a^n = a^{\frac{n}{2}} \times a^{\frac{n}{2}}$
- $n$이 홀수일 때 : $a^n = a^{\frac{n-1}{2}} \times a^{\frac{n-1}{2}} \times a$
예시를 보자.
- $2^8 = 2^4 \times 2^4$
- $2^4 = 2^2 \times 2^2$
- $2^{15} = 2^7 \times 2^7 \times 2$
- $2^3 = 2^1 \times 2^1 \times 2$
1
2
3
4
5
6
7
8
9
// 분할정복을 이용한 거듭제곱
int pow(int a, int n) {
if(n == 0) return 1;
int temp = pow(a, n/2);
int k = temp * temp;
if(n%2==0) return k;
else return k*a;
}
모듈러 연산
음수의 모듈러 연산
정수 mod n의 결과는 항상 $0 \verb|~| (n-1)$의 범위를 가지는 정수이다.
음수 $a$를 모듈러 연산은 $a \bmod n = (a+kn) \bmod n$ ($k$는 자연수)을 해야한다.
예시를 보자.
- $5 \bmod 11 = 5$
- $23 \bmod 11 = 1$
- $-5 \bmod 11 = (-5+1 \times 11) \bmod 11 = (-5+2 \times 11) \bmod 11 = \cdots = 6$
- $-23 \bmod 11 = (-23+3 \times 11) \bmod 11 = 10$
모듈러 합동
$a \bmod n = b \bmod n$이면 $a$와 $b$는 모듈러 합동 관계이고,
$a \equiv b \pmod{n}$와 같이 표기한다.
모듈러 연산의 속성
$a, b$가 양수일 때,
- $(a+b) \bmod n = \lbrace(a \bmod n)+(b \bmod n)\rbrace \bmod n$
- $(a-b) \bmod n = \lbrace(a \bmod n)-(b \bmod n)\rbrace \bmod n$
- $(a \times b) \bmod n = \lbrace(a \bmod n) \times (b \bmod n)\rbrace \bmod n$
특히 2번에서 $(a \bmod n)-(b \bmod n)$가 음수인 경우를 조심해야 한다.
따라서 2번은 $\lbrace(a \bmod n)-(b \bmod n) + n\rbrace \bmod n$으로 계산하는 것이 안전하다.
3번의 경우 곱해진 두 수를 자유롭게 모듈러 연산할 수 있다는 것이 특징이다.
\((a \times b) \bmod n = \lbrace(a \bmod n) \times b\rbrace \bmod n\) \(= \lbrace a \times (b \bmod n)\rbrace \bmod n = \lbrace(a \bmod n) \times (b \bmod n)\rbrace \bmod n\)
모듈러 곱셈의 역원
$a$의 역원을 $t$라고 할 때, $(a \times t) \bmod = 1$이다.
예를 들어, $n=11$일 때, $3$의 역원을 구하려면, $(3 \times t) \bmod 11 = 1$을 만족하는 $t$를 구하면 된다.
이때 $t$는 하나로 정해지지 않을 수 있다.($t=4, 15, 26, 37, \cdots$)
모듈러 나눗셈
$b$의 역원을 $t$라고 할 때, $\left(\cfrac{a}{b} \bmod n\right) = (a \times t) \bmod n$이다.(증명 생략)
예시
- $n=11$일 때, $3$의 역원은 $4$이므로, $\left(\cfrac{5}{3} \bmod 11\right) = (5 \times 4) \bmod 11 = 9$
- $14$의 역원을 $t$라 할 때, $(14 \times t) \bmod 11 = 1$을 만족한다.
이때 모듈러 연산의 특징으로 인해 $(3 \times t) \bmod 11 = 1$을 찾아도 된다.
따라서 $t$는 $3$의 역원이기도 하므로 $t=4, 15, \cdots$
$\cfrac{13}{14} \bmod 11 = (13 \times 4) \bmod 11 = 8$
이항계수 모듈러 연산
\[_{n}\mathrm{C}_{r} \bmod p\]파스칼의 삼각형 이용 - $O(n^2)$
이항계수의 성질인 $ \binom{n}{r} =\binom{n-1}{r-1}+\binom{n-1}{r}$을 이용해 DP Table을 만든다.
1
2
3
4
5
6
7
8
9
10
11
// bottom up 방식의 DP
int n, r;
cin >> n >> r;
for(int i=1; i<=1000; i++) {
for(int j=0; j<=i; j++) {
if(j==0 || j==i) {
c[i][j] = (c[i-1][j-1]+c[i-1][j]) % MOD;
}
}
}
cout << c[n][r];
페르마의 소정리 이용 - $O(n \log p)$
페르마의 소정리는 다음과 같다.
“소수 $p$와 정수 $a$에 대해서 $a$와 $p$가 서로소이면 $a^{p-1} \bmod p = 1$을 만족한다.”
분수꼴의 모듈러 연산은 역원을 구하는 과정이 필요하다. 따라서 $r!(n-r)!$의 역원을 찾아야 한다.
소수인 $p$는 $r!(n-r)!$와 서로소이다. (단, $p \neq r!(n-r)!$)
페르마의 소정리에 의해 $\lbrace r!(n-r)!\rbrace^{p-1} \bmod p = 1$이고,
변형하면 $\lbrace r!(n-r)!\rbrace^{p-2} \times \lbrace r!(n-r)!\rbrace \bmod p = 1$이다.
따라서 $r!(n-r)!$의 역원은 $\lbrace r!(n-r)!\rbrace ^{p-2}$이므로, 아래와 같은 식이 성립된다.
\[_{n}\mathrm{C}_{r} \bmod p = \frac{n!}{r!(n-r)!}\bmod p = n! \times \lbrace r!(n-r)!\rbrace^{p-2} \bmod p\]문제 예시
https://www.acmicpc.net/problem/13977
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#define ll long long
const int MOD = (int)1e9 + 7;
using namespace std;
ll fac[4000001], inverse[4000001];
ll factorial(ll a, ll n){
if(n==0) return 1ll;
ll temp = factorial(a, n/2);
ll k = temp*temp%MOD;
if(n%2==0) return k;
else return k*a%MOD;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, r, m;
cin>>m;
// 팩토리얼 계산
fac[0]=1;
for(int i=1; i<=4000000; i++){
fac[i]=(fac[i-1] * i)%MOD;
}
// 역원 계산
inverse[4000000] = factorial(fac[4000000], MOD - 2);
for (int i = 4000000 - 1; i >= 0; i--){
inverse[i] = inverse[i + 1] * (i + 1) % MOD;
}
while(m--) {
cin>>n>>r;
cout<<((fac[n] * inverse[r] % MOD) * inverse[n-r]%MOD)%MOD<<"\n";
}
}
전역변수
frc[n]= $n! \bmod p$inverse[n]= $(n!)^{p-2} \bmod p = $($n!$ 의 역원) $\bmod p$
역원 계산(32번 라인) \(\lbrace (n-1)! \rbrace ^{p-2} \bmod p = n \times (n!)^{p-2} \bmod p\)
nCr mod p 계산(37번 라인) \(_{n}\mathrm{C}_{r} \bmod p = n! \times \lbrace r!(n-r)!\rbrace^{p-2} \bmod p = n! \times (r!)^{p-2} \times \lbrace(n-r)!\rbrace^{p-2} \bmod p\)