글 읽기 - Python3 이항계수3, 페르마의 소정리를 이용한 풀이 WA 질문 드립니다.

0xdeadbeef 3년 전 0

안녕하세요. 문제를 접하고 어떻게 해야될지 모르겠던 도중 페르마의 소정리라는걸 알게 되었습니다.

p가 소수고 a가 정수인 경우 a^p-1≡ 1 (mod p) (a ≠ 0)가 성립한다고 하더라구요

그래서 문제의 _nC_k를 구할때 다음과 같이 식을 유도했습니다.

_nC_k ≡ (n! / (k!(n-k)!))
≡ (n! / (k!(n-k)!) * 1)
≡ (n! / (k!(n-k)!) * (k!(n-k)!)^p-1)
≡ (n! * (k!(n-k)!)^p-2) (mod p)
= ((n!%mod) * (k!%mod)^p-2 * ((n-k)!%mod)^p-2) % mod

그러나 초반 어느정도는 통과하더니 틀렸습니다가 나옵니다.

어떤 부분이 문제인걸까요? 도움 부탁드립니다. 감사합니다.

MOD = 1_000_000_007

def get_factorial(n):
    for i in range(n-1, 1, -1):
        n = (n*i)%MOD
    return n

def fast_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return (fast_pow(x, n//2) ** 2) % MOD
    else:
        return (fast_pow(x, n//2) ** 2 * x) % MOD

N, K = map(int, input().split())
A = get_factorial(N)
B = fast_pow(get_factorial(K), MOD-2)%MOD
C = fast_pow(get_factorial(N-K), MOD-2)%MOD
print(A*B*C%MOD)

0xdeadbeef 3년 전 0

엌ㅋㅋㅋ 위의 코드는 n이 0일때 factorial이 0을 반환합니다. 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Python3 이항계수3, 페르마의 소정리를 이용한 풀이 WA 질문 드립니다.

0xdeadbeef 3년 전 0

0xdeadbeef 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말