[백준 11402] 이항 계수 4 [C]

백준 - 11402

---

풀이

Fermat’s little theorem을 기반으로 한 Lucas' theorem으로 풀이했다.

 

Lucas' theorem는 다음과 같다.

위키백과 - 뤼카의 정리

쉽게, nCk를 M으로 나눈 나머지를 구하기 위해서는

N과 K를 M진 전개해 얻은 각 자릿수의 조합끼리 곱하고 M으로 나누면 된다.

 

ex) input : 100 45 13

100 = 13*7 + 1*9

 45 = 13*3 + 1*6

int result = 1;
while (N || K){
    result = result*nCk(N%M, K%M, M) %M;
    N /= M, K /= M;
}

nCk는 Fermat’s little theorem으로 구했다.

---

소스코드

#include <stdio.h>
int nCk(int N, int K, int M){
    int A = 1, B = 1;
    for (int i = N; i > N-K; i--)
        A = A*i %M;
	
    for (int i = K; i >= 2; i--)
        B = B*i %M;

    N = 1, K = M-2;
    while (K){
        if (K & 1) N = N*B %M;
        K >>= 1;
        B = B*B %M;
    }
    return A*N %M;
}
int main(){
    long long N, K;
    int M;
    scanf("%lld %lld %d", &N, &K, &M);

    int result = 1;
    while (N || K){
        result = result*nCk(N%M, K%M, M) %M;
        N /= M, K /= M;
    }
    printf("%d", result);
}

---

출처 및 참고자료

11402번: 이항 계수 4

뤼카의 정리 - 위키백과, 우리 모두의 백과사전

[백준 11401] 이항 계수 3 [C]