Processing math: 100%
반응형

https://www.acmicpc.net/problem/13977

 

13977번: 이항 계수와 쿼리

M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

 

https://rudalsd.tistory.com/61?category=1064608 

 

[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다. a0에 대하여 apa(mod p)를 만족하고, 만약 p가 소수이고, ap가 서로소이면 ap11(mod..

rudalsd.tistory.com

 

먼저 (NK)는 다음과 같이 나타낼 수 있습니다.

 

(NK)=N!(NK)!K!

 

그리고 페르마의 소정리를 이용하여 mod m에서 어떤 수를 a로 나눈다는 뜻은 a의 역원을 곱한다는 뜻과 같습니다. 따라서 m이 소수일 때, am11(mod m)이고, a×am21(mod m)이므로 mod m에서 a에 대한 곱셈의 역원은 am2입니다.

 

따라서, 

 

N!(NK)!K!N!×((NK)!K!)m2(mod m)

 

이 됩니다.

 

분모의 수로 나누는 방법 대신 m2제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이 때 m의 값이 1,000,000,007로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

 

 

[ 소스 코드 ]

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
40
41
42
43
44
45
#include<iostream>
 
#define ll long long
#define MOD 1000000007
 
using namespace std;
 
ll fac[4000001];
 
int M, N, K;
 
ll pow(ll num, int p)        //분할 정복을 이용한 거듭제곱
{
    if (p == 0return 1;
    if (p == 1return num;
 
    if (p % 2 == 0) {
        ll temp = pow(num, p / 2);
        temp %= MOD;
        return (temp * temp) % MOD;
    }
    else {
        ll temp = pow(num, p - 1);
        temp %= MOD;
        return (num * temp) % MOD;
    }
}
 
int main()
{
    fac[0= 1;
 
    for (int i = 1; i <= 4000000; i++) {
        fac[i] = fac[i - 1* i;
        fac[i] %= MOD;
    }
 
    scanf("%d"&M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d"&N, &K);        //페르마의 소정리
        ll ans = (fac[N] * pow((fac[N - K] * fac[K]) % MOD, MOD - 2)) % MOD;
        printf("%lld\n", ans);
    }
}
cs
반응형
반응형

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다.

 

a0에 대하여 apa(mod p)를 만족하고,

만약 p가 소수이고, ap가 서로소이면 ap11(mod p)를 만족한다.

 

수학적 귀납법을 이용하여 위의 식을 증명해보겠습니다.

먼저, 0ap1 범위의 정수에서만 증명해도 충분합니다. 그 이유는 ap로 나눈 나머지는 항상 0보다 크거나 같고 p1보다 작거나 같기 때문입니다.

 

1. a=0일 때

 

a0인 경우에는 0p=00(mod p)

 

2. a=k일 때 성립한다고 가정하고 a=k+1일 때

 

a=k일 때 성립한다고 가정했으므로, kpk(mod p)를 만족합니다.

이항 정리를 사용하여 a=k+1일 때도 성립함을 증명합니다.

 

(k+1)p=pi=0(pi)ki

 

이때 이항 계수의 정의에 의해서

 

(pi)=p!(pi)!i!=p(p1)(pi+1)i(i1)1

 

이고, 위 식은 1ip1일 때 p의 배수이므로 p로 나누면 없어지게 됩니다. 또한, i0 또는 p이면 1입니다. 따라서,

 

(k+1)p(p0)k0+(pp)kp=kp+1k+1(mod p)

 

a=k+1일 때도 성립함을 증명했습니다. 따라서,따라서, a0에 대하여 apa(mod p)를 만족합니다.

 

ap가 서로소인 경우는 다음과 같이 유도할 수 있습니다.

 

apa(mod p)이므로, apa=a(ap11)p로 나누어 떨어집니다. 이때, ap가 서로소이므로 ap11p로 나누어 떨어집니다.

 

따라서, ap11(mod p)를 만족합니다.

반응형

+ Recent posts