[BOJ][python] 13172. ∑

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

13172번: Σ

---

💡IDEA

분할 정복과 수학을 사용하는 문제이다.

이 문제를 이해하려면, 일단 모듈로 곱셈 역원에 대해 알아야 한다. 학부 때의 기억을 되살리느라 힘들었다.

문제에서 자세히 설명해주고 있는 것 같지만, 문제만 봐서는 잘 이해가 되지 않을 것이다.

중요한 부분은 다음 내용이다.

어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 $a × b^{-1} (mod X)$ (X는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$은 b의 모듈러 곱셈에 대한 역원이다. b의 모듈러 곱셈에 대한 역원 $b^{-1}$은 $b^{-1} × b \equiv 1 (mod X)$ 을 만족하는 정수이다. 소수 모듈러에서만 성립하는 페르마의 소정리에 의해 $b^{X - 1} \equiv 1 (mod X)$가 성립하기에, $b^{X - 2} \equiv b^{-1} (mod X)$ 역시 성립함을 알 수 있다.

 

예를 들어, a = 7, b = 3, X = 11인 경우를 생각해보자.

7/3을 모듈러 11로 나타내어본다면, 이 분수는 $7 × 3^{-1} (mod 11)$다.

이 때 $3^{-1}$은 페르마의 소정리에 의해 $3^{11-2} (mod 11)$로 알 수 있다. $3^{11-2} (mod 11)$는 1629번, 10830번을 풀 때와 같이 분할 정복으로 제곱을 쪼개며 모듈러 처리해주면 된다.

이 문제는 기댓값을 구하기 위해 $S_i / N_i$을 계산해야 하는데, 위에 설명한 것 처럼 $S_i × N_i^{-1} (mod 1000000007)$을 계산한 값을 출력하면 된다.

 

📌CODE

import sys
input = sys.stdin.readline

M = int(input())
dices = []
mod = 1000000007
ans = 0

def pow(a, b):
    if b == 1:
        return a % mod
    tmp = pow(a, b // 2)
    if b%2:
        return a*tmp*tmp%mod
    else:
        return tmp*tmp%mod

for _ in range(M):
    Ni, Si = map(int, input().split())
    ans += Si*pow(Ni, mod-2)%mod
print(ans%mod)