(Python/🥇1)백준알고리즘 11401번: 이항계수 (합동식, 모듈러 연산, 페르마의 소정리)

 

문제 바로가기 

문제:

입력:

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

 

출력:

 (𝑁/𝐾) 를 1,000,000,007로 나눈 나머지를 출력한다.

 

풀이:

 

실패 1 런타임 에러: 

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)
def fibo(n, k):
    if k == 0 or n == k:
        return 1
    return fibo(n-1, k) + fibo(n-1, k-1)


n, k = map(int,sys.stdin.readline().split(" "))
print(fibo(n,k))

 

 

이 문제는 예전부터 못 풀었기 때문에 여러 블로그와 유튜브를 참고했다.

 

합동식 : 정수 a, b 를 p로 나눈 나머지가 같을때 a==b(mod)p 라고 한다.

1. 같은 수를 양 변에 더하거나 빼도 합동식이 성립한다.
   1.  a +- k == b +- k(mod)p
2. 같은 수 (정수) 를 곱해도 가능하다
   1. ak == bk(mod)p
3. 같은 수 로 나눠도 가능하다.
   1. a = b(mod)p
   2. a/k = b/k(mod* p/gcd(k,p))      cf) gcd 최대 공약수
4. 같은 거듭제곱을 해도 가능

 

모듈러 연산

 

어떠한 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

A를 B로 나누어 나머지가 C가 나왔다면 "A mod B = C" 또는 "A % B = C"

(a + b) % m = ((a % m) + (b % m)) % m

(a - b) % m = ((a % m) - (b % m)) % m

(a * b) % m = ((a % m) * (b % m)) % m

 

 

페르마의 소정리

 

결론 a^p-1 = 1(modp)

 

 

A + P 이고 (a는 정수, p는 소수)

정수를 P로 나누면 나머지는 0,1,2,3,...p-1 로 P가지의 수가 나타낼수있다.

 

a, 2a, 3a ... (p-1)a

p-1개의 수는 p로 나눈 나머지가 모두 다르다.

 

다른 수 를 뽑아서 만약 같다고 하면, a= b로 두 수가 같게 된다.

 

 

이 문제는 모듈러 연산과, 페르마의 소 정리를 이용하면 된다.

 

(A / B) % p =

(A * B^(p-2)) % p =

((A % p) * (B^(p-2) % p)) % p

 

이거를 문제에 대입하면 된다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)

def fac(N, rest):
    n = 1
    for i in range(2, N+1):
        n = (n * i) % rest
    return n

# 거듭제곱 계산 (나머지 연산 적용)
def reduce_pow(a, b, c):
    if (b == 1):
        return a % c

    X = reduce_pow(a, b//2, c)

    if (b % 2 == 0): # 짝수라면
        return X * X % c
    else: # 홀수라면
        return a * X * X % c


N, K = map(int, input().split())
P = 1000000007

TOP = fac(N, P)

BOTTOM = fac(K, P) * fac(N-K, P)

print(TOP * reduce_pow(BOTTOM , P-2, P) % P)