[BOJ][Python]13172 풀이

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

13172번: Σ

import sys
input = sys.stdin.readline
X = 1_000_000_007 # 자릿수 구분할 때 언더스코어를 사용해도 됨

def get_ni(n, x):
    result = 1
    while x > 0:
        if x % 2 == 1:
            result = result * n % X
        n = n * n % X
        x //= 2
    return result

m = int(input())
ans = 0
for _ in range(m):
    n, s = map(int, input().split()) # n이 분모, s가 분자
    # n * ni % 1000000007 = 1 = ((n % 1000000007) * (ni % 1000000007)) % 1000000007
    # 페르마의 소정리에 의해 ni = n^(x-2)%x
    ni = get_ni(n, X-2)
    ans += ni * s % X
print(ans % X)

이번에는 지문이 꽤 긴 문제입니다. 저는 이렇게 지문이 긴 문제가 나오면 메모장에 복사해서 필요없겠다 싶은 부분을 계속 지워나가면서 읽는 편입니다. 그런 작업을 몇 번 거치고 나면 글도 여러번 읽게 되고, 불필요한 부분을 날려버리면서 좀 더 문제가 이해가 잘 되더라구요.

 

그래서 이번 문제에서 요구하는 것은 전에 했었던 '분할정복을 이용한 거듭제곱을 할 줄 아는가' & '모듈러 연산의 성질을 알고 있는가'입니다. 중간 중간에 계속 나머지 연산을 진행하지 않으면 수가 너무 커져서 시간 초과가 나니까요. 그래서 $ (a * b) \bmod\ c = ((a \bmod\ c) * (b \bmod\ c)) \bmod\ c $임을 알고 연산과정에서 계속 나머지 연산을 진행해줘야 합니다(덧셈과 뺄셈도 동일).

 

그리고 이건 저도 몰랐는데 보통 수를 표현할 때 숫자가 커지면 천의 자리마다 쉼표를 찍어서 표시를 하는데, 코드를 짤 때는 쉼표를 찍으면 에러가 나길래 이 때 까지는 숫자를 세어가면서 작성을 했었습니다. 근데 언더스코어를 쉼표처럼 사용하면 신택스 에러 없이 작성이 가능하더라구요. 좋은 팁인 것 같아서 같이 작성해봅니다.