[Python] 백준13172 시그마

22 Jun 2023 in Study on Algorithm

백준13172 시그마 링크

문제

예제 입력

---

코드

import sys
X = 1000000007
m = int(input())

def sol(b, x):
    if x == 1:
        return b % X
    else:
        if x % 2 == 0:
            tmp = sol(b, x//2)
            return (tmp * tmp) % X
        else:
            return b * sol(b, x-1) % X
        
ans = 0
for _ in range(m):
    n, s = map(int, sys.stdin.readline().split())
    Q = s * sol(n, X-2) % X
    ans += Q
    ans %= X

print(ans)

# 모듈러 연산
# 파이썬처럼 오버플로우가 발생하지 않는 언어를 쓰더라도 매우 큰 수를 곱하는건 
# FFT(고속 푸리에 변환)이라는 알고리즘을 사용해서 시간이 오래 걸림.
# 그래서 중간에 나머지를 구해 오버플로우 발생 불가.

# (a+b)%p = ((a%p)+(b%p))%p
# (a*b)%p = ((a%p)*(b%p))%p
# (a-b)%p = ((a%p)-(b%p)+p)%p
# (a/b)%p =/ ((a%p)/(b%p))%p

# 페르마의 소정리
# a^p = a (mod p)
# a^(p-1) = 1 (mod p)
# a^(p-2) = 1/a (mod p)

# X = 11, Q = 7/3
# 3**(-1) = 4 (mod 11)
# a/b = a * b**(-1) = a * b**(x-2) mod x
# 7/3 = 7 * 4 = 28 % 11 = 6

설명

파이썬을 통해서 사용자로부터 입력받아 분할 정복알고리즘을 사용하여 시그마를 구현했습니다.

---

결과