[Python] 13172번 Σ

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

---

 

24/05/29

 

 

클래스에 있던 문제 중에 하나로, 간단한 정수론 문제이다.

---

 

문제 접근 방식:

 

 

친절하게도, 문제에 대한 답이 다음과 같이 써져있다.

 

$$\frac{S_1}{N_1} + \frac{S_2}{N_2} + \cdots + \frac{S_M}{N_M}$$

 

이를 그대로 구현해주면 된다.

 

이때, 답은 기약분수로 나타내야 하므로, $S_i$와 $N_i$를 입력받을 때마다, $\text{gcd}(S_i, N_i)$로 두 수를 나눠준다.

 

또한, 모듈로 역원은 파이썬에서는 pow함수의 지수부분에 -1을 넣음으로써 쉽게 구할 수 있으므로 이를 활용하면 쉬워진다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 13172번 Σ
# 정수론, 모듈로 곱셈 역원
import sys
input = sys.stdin.readline
from math import gcd
MOD = 1_000_000_007
# 주사위의 수
M = int(input())
ans = 0
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a//gcd(a,b), b//gcd(a,b)
    ans += (b*pow(a,-1,MOD))%MOD
    ans %= MOD
print(ans)