코딩테스트 대비/BOJ
[Baekjoon/Python] 13172번: Σ - 효과는 굉장했다!
bluetag_boy
2022. 7. 24. 18:28
반응형
import sys
import math
mod = int(1e9+7)
def Divide_and_Conquer(num, exp):
if exp == 1: # 기댓값이 1 이면
return num
if exp % 2 == 0:
half = Divide_and_Conquer(num, exp//2)
return half * half % mod
else:
return num * Divide_and_Conquer(num, exp-1) % mod
M = int(sys.stdin.readline())
total = 0
for _ in range(M):
N, S = map(int, sys.stdin.readline().split())
gcd = math.gcd(N, S) # 최대공약수
N //= gcd
S //= gcd
total += S * Divide_and_Conquer(N, mod-2) % mod
total %= mod
print(total)13172번: Σ
모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.
www.acmicpc.net
알고리즘 분류
- 수학
- 정수론
- 분할 정복을 이용한 거듭제곱
- 모듈로 곱셈 역원
- 페르마의 소정리
SOLUTION
import sys
import math
mod = int(1e9+7)
# 분할 정복
def Divide_and_Conquer(num, exp):
if exp == 1: # 기댓값이 1 이면
return num
if exp % 2 == 0:
half = Divide_and_Conquer(num, exp//2)
return half * half % mod
else:
return num * Divide_and_Conquer(num, exp-1) % mod
M = int(sys.stdin.readline())
total = 0
for _ in range(M):
N, S = map(int, sys.stdin.readline().split())
gcd = math.gcd(N, S) # 최대공약수
N //= gcd
S //= gcd
total += S * Divide_and_Conquer(N, mod-2) % mod
total %= mod
print(total)