[백준 13977번 C/C++] 이항 계수와 쿼리

 

[백준 13977번 C/C++] 이항 계수와 쿼리

 

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

13977번: 이항 계수와 쿼리

---

 

 

해결전략

 

수학
소페르마 정리

고민하다 힌트를 보았다. 소페르마 정리를 모르면 풀기 힘든 문제였다. 소페르마 정리를 읽고 공식을 코드를 구현하면 되었다. 

---

 

정답 코드

 

#include <iostream>
using namespace std;
long long factorial[4000001];
long long MOD = 1000000007;

long long CustomPow(long long num, long long x)
{
	if (x == 0) return 1;
	else if (x == 1) return num;
	else if (x % 2 == 0) {
		long long temp = CustomPow(num, x / 2);
		return (temp * temp) % MOD;
	}
	else {// x % 2 == 1
		long long temp = CustomPow(num, x - 1);
		return (temp * num) % MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int m, n, k;
	cin >> m;

	// factorial 미리 구해놓기
	factorial[0] = 1;
	for (int i = 1; i < 4000001; i++) {
		factorial[i] = factorial[i - 1] * i;
		factorial[i] %= MOD;
	}

	for (int i = 0; i < m; i++) {
		cin >> n >> k;
		long long up = factorial[n];
		long long down = (factorial[k] * factorial[n - k]) % MOD;

		down = CustomPow(down, MOD - 2) % MOD; // 페르마의 소정리

		cout << (up * down) % MOD << '\n';
	}

	return 0;
}

 

---