백준 11401 이항 계수 3 - 파이썬

문제.

풀이.

페르마의 소정리를 이용하여 풀었다.

유클리드 확장법을 통하여서도 풀 수 있다고 한다.

우선 문제를보면 1,000,000,007은 소수이다.

페르마의 소정리는

p가 소수이고 a가 p의 배수가 아니면 a^(p-1) = 1 mod p 이다

더 자세한 내용은 https://www.acmicpc.net/board/view/15795 해당 링크를 참조해서 보면 될 것 같다.

 

소스코드.

import sys

def div_con(n, p):
    prime = 1000000007
    if p == 0:
        return 1
    temp = div_con(n, p//2)
    if p % 2 == 0:
        return (temp * temp) % prime
    elif p % 2 == 1:
        return (temp * temp * n) % prime

p = 1000000007
N, K = map(int, sys.stdin.readline().split())
factorial = [0] * (N+1)
factorial[0:1] = 1, 1
for i in range(2,N+1):
    factorial[i]  = factorial[i-1] * i % p
a = factorial[N]
b = factorial[K] * factorial[N-K]
result = ((a % p) * div_con(b % p, p-2)) % p
print(result)