[백준/C++] 11401번 - 이항 계수 3

문제

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

 

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

 

 

 

입력

 

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

 

 

출력

 

(N, K)를 1,000,000,007로 나눈 나머지를 출력한다

 

 

풀이

 

이항계수는 nCk로 쉽게 구할 수 있는데, 곱셈간의 나머지를 구하기는 쉽지만 나눗셈이 포함 될 경우 나머지를 계산하기가 어렵기 때문에 페르마의 소정리를 이용해서 풀었다.

 

페르마의 소정리 증명

 

$$a^{p-2} \equiv a^{-1} \pmod{p}$$

 

페르마의 소정리를 참고하면 위와 같이 나타낼 수 있다.

 

그러므로 nCk를 n!/a 로 표현하고 a부분을 페르마의 소정리를 이용해 나머지를 구하면 된다.

 

즉,

$$\frac{n!}{a} \pmod{p} \equiv n!*a^{p-2} \pmod{p}$$

라는 것이다.

 

이 때 a = (n-k)!*k! 이다. a를 p-2번 제곱한 수의 나머지를 구하는 방법은 절반씩 나눠가며 재귀로 구했다.

 

 

Code

 

 

#include<iostream>
using namespace std;

// 11401
const long long mod_num = 1000000007;

long long N, K;

long long binary_mod(long long num, int cnt) {
	if (cnt == 1) {
		return num % mod_num;
	}
	int mid = cnt / 2;
	long long c = binary_mod(num, mid);
	long long renum = 0;
	if (cnt % 2==1) {
		renum = c * c;
		renum%=mod_num;
		renum *= num;
		return renum%=mod_num;
	}
	else {
		renum = c * c;
		return renum %= mod_num;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	//A=n!, B=(n-k)!*k!
	long long A=1;
	long long B=1;
	for (int i = 1; i <= N; i++) {
		A *= i;
		A = A % mod_num;
	}
	for (int j = 1; j <= K; j++) {
		B *= j;
		B %= mod_num;
	}
	for (int j = 1; j <= N-K; j++) {
		B *= j;
		B %= mod_num;
	}
	long long ans = binary_mod(B, mod_num - 2);
	ans = ans * A;
	cout << ans % mod_num;
	return 0;
}

 

---

 

이 문제는 다시 풀라고 해도 페르마의 소정리를 가져다 주면서 이걸 활용해서 풀어라 라고 말하지 않는 이상 바로 푸는 방법이 생각나지 않을 것 같다;

 

페르마의 소정리를 배운 적이 없는데 문제를 보고 어떻게 바로 푸냐고...