[c++] 백준 11401 - 이항 계수 3(페르마의 소정리, 확장 유클리드 호제법, 베주 방정식)

0. 주어진 문제

이항 계수 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	3827	1543	1148	49.633%

문제

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $(\genfrac{}{}{0ex}{}{N}{K})$를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 4,000,000, 0 ≤ $K$ ≤ $N$)

출력

 $(\genfrac{}{}{0ex}{}{N}{K})$를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1 

5 2

예제 출력 1 

10

1. 풀이

우선, 이항 계수를 정의하는 방법을 생각해보자.

먼저 생각나는 것은 이항계수2(https://kyunstudio.tistory.com/56)에서 구한 점화식 형태이다.

의 방식을 활용하는 것이다.

이 경우는 재귀호출법을 이용해 구현을 할 수 있었다. 허나 이 식의 복잡도는 으로 10억이 넘는 수를 계산하니 시간 제한을 넘길 수 밖에 없었다.

그래서 다른 방법을 찾아보았는데, 이항 계수의 정의을 활용하는 것이었다.

하지만, 이 식을 활용하면 답을 빠르게 구할 수 있을 것 같은 예감이 드는데, 아직 몇가지 단계를 더 거쳐야 한다.

왜냐하면, 분수의 형태에는 mod가 각각 나눠지는 것이 불가능 하기 때문이다.(분모가 0이 되어버리므로)

따라서 형태를 형태로 바꿔주는 연산이 필요하다.

여기서 페르마의 소정리를 활용하게 된다. 페르마의 소정리는 

$p$가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1 \left( \text{mod}\ p \right)$ 이다. 즉, ${a}^{p-1}$을 p로 나눈 나머지는 1이다.

인데, 여기서 다시 생각해보면, 이라는 소리이다.

위의 식을 활용하면,  이 성립하게 된다.

따라서, 주어진 입력은 4,000,000으로 팩토리얼을 구하는 연산은 O(n)에 끝낼 수 있고, 제곱을 구하는 연산은 분할정복을 통해 O(log n)에 수행할 수 있으므로, 1초 안에 수행이 가능하게 된다.

+) 추가적으로

확장 유클리드 방정식(참고)과 베주 방정식이라는 것을 활용하는 방법도 있었다.

적어도 둘 중 하나는 0이 아닌 정수 $a, b$가 있다. 그리고 $a$와 $b$의 최대공약수를 $d$라고 하자. 이때, 다음 세 명제가 성립한다. 1. $d= ax + by$를 성립하게 만드는 정수 $x, y$가 반드시 존재한다. 2. $d$는 정수 $x, y$에 대하여 $ax+by$ 형태로 표현할 수 있는 가장 작은 자연수이다. 3. 정수 $x, y$에 대하여 $ax+by$ 형태로 표현되는 모든 정수는 $d$의 배수이다.

이 항등식을 활용하는 방법을 알아보자.

우선, 우리가 해야하는 목표는 분모 부분을 없에는 방법을 찾는 것이다. 이 분모를 라 하자.

우리에게 주어진 1,000,000,007이라는 수는 10억이 넘는 수 중에서 가장 작은 소수라는 특성을 가지고 있다. 즉 B와 q는 서로소라는 소리이다. 즉 최대 공약수는 1이 된다.

따라서, 가 성립하게 된다. 여기에 %p를 취해보자.(이때, B는 처음 식의 분모 부분)

이 성립한다는 뜻이다.

즉, 처음 주어진 식 에 이를 대입하면, 가 된다.

이때, x는 유클리드 확장 방정식을 활용하여 구해낼 수 있다.(참고)

확장 유클리드 호제법에 따르면

인 식이 주어질 때, 

이다.(p>b 이므로)

이 초기값을 가지고의 값이 0이 될때까지 점화식을 이어나가면 x의 값을 구할 수 있게 된다.

보기 쉽게 표로 만들어보자면,

	x	y	r	p
i=0	0	1	p(1,000,000,007)
i=1	1	0	B(K!*(N-K)!)	p/B
i=2	0 - 1*[p/B]	1 - 0*[p/B]	p%B	[p%B]/B

2. 소스코드

페르마의 소정리를 활용한 코드

#include <cstdio>
#include <algorithm>
#define P 1000000007LL
typedef long long ll;
using namespace std;
ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse
ll power(ll x, ll y) {    //분할 정복을 이용하여 x^y 구하기
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= P;
        }
        x *= x;
        x %= P;
        y /= 2;
    }
    return ret;
}
int main() {
    fac[1] = 1;
    for (int i = 2; i <= 4000000; i++)
        fac[i] = (fac[i - 1] * i) % P;            //factorial 전처리
    inv[4000000] = power(fac[4000000], P - 2);    //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리) 
    for (int i = 4000000 - 1; i > 0; i--)
        inv[i] = (inv[i + 1] * (i + 1)) % P;    //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리
    //총 O(N+logP)시간에 전처리를 끝냄 
    //전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능
    scanf("%lld%lld", &n, &k);
    if (n == k || !k) {
        puts("1");
        return 0;
    }
    ll r = (fac[n] * inv[n - k]) % P;
    r = (r*inv[k]) % P;
    printf("%lld\n", r);
    return 0;
}

확장 유클리드 호제법

#include <iostream>
 
const long long p = 1000000007;
long factorial[4000000];
long x_after, x_before, temp, q;
 
void euclidean(long p,long B) {
    if (p%B > 0) {
        euclidean(B, p%B);
        temp = x_after;
        x_after = x_before - (p/B)*x_after;
        x_before = temp;
    }
    else {
        x_after = 1;
        x_before = 0;
    }
}
 
int main() {
    int N, K;
    std::cin >> N >> K;
    factorial[0] = factorial[1] = 1;
    for (int i = 2; i <= N; i++) 
        factorial[i] = (factorial[i - 1] * i) % p;
 
    long B = (factorial[K] * factorial[N - K]) % p;
 
    euclidean(p, B);
    long result = ((factorial[N] % p)* (x_after%p)) % p;
    if (result < 0) result += p;
    std::cout << result << std::endl;
}

3. 문제 출처

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

4. 참고

(참고할때 위키까지 읽어보시길)

페르마의 소정리를 활용한 풀이

- https://www.acmicpc.net/board/view/15795

- https://namu.wiki/w/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98%20%EC%86%8C%EC%A0%95%EB%A6%AC

확장 유클리드 방정식과 베주 항등식을 활용한 풀이

- https://onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/

- https://namu.wiki/w/%EB%B2%A0%EC%A3%BC%20%ED%95%AD%EB%93%B1%EC%8B%9D

확장 유클리드 방정식 코드

-https://codepractice.tistory.com/79