알고리즘/수학
2021. 3. 11.
기초 정수론2
페르마의 소정리 p가 소수이고, gcd일 때 a^{p-1} \equiv 1 \mod p 앞선 글에서 모듈러 역원을 구하는데 확장 유클리드 알고리즘을 이용할 수 있다는 사실을 알았습니다. 그런데 모듈러가 소수라면, 조금 더 간단하게 모듈러 역원을 구할 수 있습니다. 페르마의 소정리에 따르면, p가 소수일 때 p와 서로소인 임의의 a의 모듈러 역원은 a^{p-2}입니다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 N과 정수 K가 주어졌을 때 이항 계수 \binom{N}{K}를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.ne..
