[Python] 백준 13172번: ∑

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

13172번: Σ

 

import sys
import math
input = sys.stdin.readline
X = 1000000007


def getExpectedValue(n, s):
    return s * getSquaredNumber(n, X-2) % X


def getSquaredNumber(num, exp):
    if exp == 1:
        return num

    if exp % 2 == 0:
        half = getSquaredNumber(num, exp//2)
        return half * half % X
    else:
        return num * getSquaredNumber(num, exp - 1) % X


if __name__ == '__main__':
    M = int(input())

    sum = 0
    for _ in range(M):
        n, s = map(int, input().split())
        gcd = math.gcd(n, s)
        n //= gcd
        s //= gcd

        sum += getExpectedValue(n, s)
        sum %= X

    print(sum)

 

중요한 내용들은 다음과 같다.

 - b^(X - 2) ≡ b^(-1) (mod X)

 - (기댓값) = (a × b^(-1)) mod 1,000,000,007

 

X가 1,000,000,007이므로 이것을 정리하면 다음과 같다.

(기댓값) = (a × b^(1,000,000,005)) mod 1,000,000,007

 

여기서 1000000005제곱을 구하는 것이 관건이다. 해당 연산은 분할정복으로 해야 시간초과를 면할 수 있다.