BOJ13172. Σ

작성일

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

  • 앞서 푼 13171의 코드를 이용하는 문제.
  • 확장 유클리드를 이용하는 문제이다. $M$이 소수일때 $b^{-1} = b^{M-1}$임을 이용하는 문제.
  • 자세한 설명은 아예 문제에 적혀있음 -_-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MOD = 1_000_000_007

def pow(base, p):
    ans = 1
    cur = base % MOD
    while p > 0:
        ans = (cur * ans) % MOD if (p & 1) else ans
        cur = (cur * cur) % MOD
        p //= 2
    return ans

M, ans = int(input()), 0
for _ in range(M):
    a, b = (int(x) for x in input().split())
    ans = (ans + b * pow(a, MOD-2) % MOD) % MOD
print(ans)