반응형
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)'코딩테스트 대비 > BOJ' 카테고리의 다른 글
| [Baekjoon/Python] 14938번: 서강그라운드 - 효과는 굉장했다! (0) | 2022.07.24 |
|---|---|
| [Baekjoon/Python] 14502번: 연구소 - 효과는 굉장했다! (0) | 2022.07.24 |
| [Baekjoon/Python] 12851번: 숨바꼭질 2- 효과는 굉장했다! (0) | 2022.07.24 |
| [Baekjoon/Python] 11404번: 플로이드 - 효과는 굉장했다! (0) | 2022.06.12 |
| [Baekjoon/Python] 10830번: 행렬 제곱 - 효과는 굉장했다! (0) | 2022.06.12 |