프로그래밍 공부 노트

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 각 N_i와 S_i가 매우 크고, 또 MOD = 1000000007의 값이 매우 크므로 S_i / N_i를 페르마의 소정리, 즉 소수 p와 p의 배수가 아닌 자연수 a에 대해, a ^ (p - 1) ≡ 1 (mod p)를 이용해야 한다. N_i를 p - 1, 즉 MOD번 제곱한 값이 1이 되므로, N_i ^ (p - 2)는 N_i에 대한 곱셈의 역원이 된다. 따라서 모든 N_i와 S_i에 대해, S_i * (N_i ^ (MOD - 2))를 모두 더한..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net N과 K의 범위가 매우 크므로 페르마의 삼각형을 사용할 수는 없으므로, 이항계수 nCk = n! / (k! * (n - k)!)를 이용해야 한다. 단 n!, k!, (n - k)! 역시 매우 큰 값이므로, 각각을 MOD = 1,000,000,007로 나눈 값을 저장해야 한다. 각 팩토리얼을 한 값에 모듈러 연산을 취했기 때문에, n! / (k! * (n - k)!) 공식을 그대로 이용할 수는 없다. 따라서 페르마의 소정..