알고리즘/수학
2021. 3. 11.
기초 정수론2
페르마의 소정리 \(p\)가 소수이고, \(\gcd(p, a) = 1\)일 때 $$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..