[백준 13172] Σ

문제 

https://www.acmicpc.net/problem/13172

13172번: Σ

---

아이디어

페르마의 소정리를 이용해서 풀 수 있다. 

 

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

여기서 $b^{-1}$ 은 b의 모듈러 곱셈에 대한 역원이다.

 

m이 소수이기 때문에 b의 모듈러 곱셈에 대한 역원은 $b^{m-2} \text{mod m}$이 된다. 이를 f 라는 함수를 이용해서 계산한다.

 

operation 함수를 이용해서 주어진 분수를 기약분수 b/a 로 나타낸 수 $a \times b^{-1} \text{mod X} $를 계산한다. 

 

그리고 각각의 $S_i/N_i$의 합을 구해주고, 그 값을 1,000,000,007로 다시 나눈 나머지를 구하면 된다. 

 

 

 

---

Solution

import math 
m = 1000000007
def f(a, b) : 
    if b == 1 : 
        return a % m
    else : 
        rec = f(a, b//2)
        if b % 2 == 0 : 
            return rec**2%m
        else : 
            return a*rec**2%m

def operation(a, b) : 
    gcd_value = math.gcd(a, b) 
    a //= gcd_value
    b //= gcd_value 

    return b * f(a, m-2) % m

n = int(input()) 

answer = 0 

for _ in range(n) : 
    x, y = map(int, input().split())
    answer += operation(x, y)

print(answer%m)