MingyuPark

문제 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 아이디어 페르마의 소정리를 이용해서 풀 수 있다. 어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 $a \times b^{-1} \text{mod X}$ (X는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$ 은 b의 모듈러 곱셈에 대한 역원이다. m이 소수이기 때문에 b의 모듈러 곱셈에 대한 역원은 $b^{m-2} \text{mod m}$이 된다. 이를 f 라는 함수를 이용해서 계산한다. operation 함수를 이용해서 ..