[백준/BOJ] 11401 - 이항 계수 3 (c++) (페르마의 소정리, 분할정복)

1. 문제

www.acmicpc.net/problem/11401

---

2. 풀이

 

제일 오른쪽 수식에서의 분모가 0이 될 수 있는 가능성이 있기에 저렇게는 사용불가능하다.

 

여기서 페르마의 소정리가 쓰이는데

 

a^(p - 1) = 1 (mod p)는 합동식으로써 쉽게

 

a^(p - 1) mod p = 1 mod p과 같은 식이라고 생각하면 된다.

 

그래서

 

a^(p - 1) = 1 (mod p)

↓

a * a^(p - 2) = 1 (mod p)

↓

a^(p - 2) = a^-1 (mod p)이라고 볼 수 있다.

 

결론적으로

를 구하면되고 지수부분이 굉장히 크기 때문에

 

분할정복을 통해 제곱연산을 실행하면 시간내에 풀 수 있다.

 

분할정복을 통한 제곱연산 풀이:

zcacoding.tistory.com/2

백준 1629 - 곱셈 (c++) (분할정복)

---

 

3. 소스코드

#include <stdio.h>

typedef long long ll;

#define c 1000000007

int n, k;

ll power(ll n, ll m) {
	if (m == 0) return 1;
	ll tmp = power(n, m / 2);
	ll res = tmp * tmp % c;
	if (m % 2) return res * n % c;
	return res;
}

int main() {
	ll nfac = 1, kfac = 1;
	scanf("%d %d", &n, &k);
	for (int i = 1;i <= n;i++) {
		nfac *= i;
		nfac %= c;
	}
	for (int i = 1;i <= k;i++) {
		kfac *= i;
		kfac %= c;
	}
	for (int i = 1;i <= n - k;i++) {
		kfac *= i;
		kfac %= c;
	}
	kfac = power(kfac, c - 2);
	printf("%lld", nfac * kfac % c);
}

---

4. 참고

합동식

namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D

합동식 - 나무위키

페르마의 소정리

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

페르마의 소정리 - 나무위키

---

질문, 고칠점 등 댓글 언제나 환영입니다.