11401 (1) 썸네일형 리스트형 백준 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) .. 이전 1 다음
