[CLASS 4]백준 13172번 - Σ

13172번 : Σ

 

 

문제가 정말 길고 비문학을 읽는 듯한 기분을 주지만 다른 지식 필요없고 문제만 풀고 싶다면 집중해야할 부분은 정해져 있다.

 

 

문제를 열심히 읽다보면 어쨌든 b의 모듈러 곱셈에 대한 역원 (b^-1)을 구해야 한다는 것을 깨달을 수 있는데, 그 값은 (b^x-2)%x 를 통해 얻을 수 있다고 한다. 이 부분만 캐치했다면 어떻게든 문제는 풀어낼 수 있다.

 

내 코드:

from sys import stdin
from math import gcd
input = stdin.readline

mod = 1_000_000_007
ans = 0

# 거듭제곱
def multi(x,y):
    if y == 1: return x
    if y%2 : return x * multi(x,y-1) % mod
    t = multi(x, y // 2)
    return t * t % mod

for _ in range(int(input())):
    n,m = map(int,input().split())
    # 기약분수 만들기
    g = gcd(n,m)
    n //= g
    m //= g
	
    # 모듈러 역원 구해서 더하기
    ans += m * multi(n,mod-2) % mod
    ans %= mod

print(ans)

 

하나 주의할 점은 mod 값이 10억이 넘는 큰 값이므로 거듭제곱 시 분할정복을 이용해야 한다는 점이다. 안그러면 하나 구할때도 한참 걸린다.