[백준] 골5 - Σ

13172번: Σ

문제 설명

입력 갯수가 주어지고 각 입력마다 분모와 분자(즉, 분수)가 주어진다.

모든 분수들의 합을 구하는 문제이다.

단, 조금 복잡한 처리를 통해 분수를 나타낸다.

어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 a × b^(-1) mod X (X는 소수)으로 대신 계산하도록 한다.

이렇게 계산된 결과를 출력한다.

X는 1,000,000,007이다.

풀이

몇 가지 성질을 나열하겠다.

• b^(-1)의 의미

  

• 페르마의 소정리

  

즉 문제를 풀기 위해서는

// a는 분모 b는 분자
(b * GetInverse(a))

를 계속 더해야 하고

GetInverse함수는 페르마의 소정리를 통해 거듭제곱 형식으로 나타낸다.

// return <- n^(mod-2)
ll GetInverse(ll n)
{
	return Npow(n, MOD - 2) % MOD;
}