✅ BOJ 13172 - pow 연산 (분할정복 거듭제곱, 모듈러 역원)

문제 요약

m개의 (n, s) 쌍이 주어진다. 각 쌍은 n면체 주사위 굴려서 s가 나올 확률이라고 보면 되고, 결국 s/n 값을 다 더해서 mod 10^9+7로 출력하라는 소리다. 문제 자체는 그냥 기댓값들의 합을 구하라는 말처럼 생겼지만, 정수 나눗셈에 mod 연산 들어간 순간 얘기는 달라진다. 이건 무조건 모듈러 역원 문제로 바뀌는 거다.

접근 방식

s / n mod MOD는 곧 s * n^-1 mod MOD로 바꿔야 한다. 여기서 n^-1은 역원인데, MOD가 소수니까 그냥 n^(MOD-2) mod MOD로 구하면 끝난다. 이건 페르마 소정리 공식 그대로 쓴 거고, 빠르게 계산하려면 분할정복 거듭제곱 써야 한다. pow 함수 쓰면 되지만 연습하려면 직접 구현해도 된다. 분할정복 문제이니 만큼 이 부분을 직접 구현하면서 이해하는게 좋다.

주의할 점

곱셈할 때도 mod 처리 안 하면 값 터진다. 누적합 더할 때도 mod 걸어줘야 안전하게 간다. pow 함수는 언어에 따라 없을 수도 있으니 직접 짜는 연습 해두는 게 좋고, 파이썬은 그냥 pow(a, b, mod) 쓰면 빠르고 깔끔하다.

핵심 개념

정수 나눗셈에 mod 들어오면 무조건 모듈러 역원으로 처리해야 하고, MOD가 소수일 때만 페르마 소정리 써서 역원 구할 수 있다.

분할정복 거듭제곱은 a를 제곱하면서 b를 절반씩 줄이고, b의 비트가 1일 때만 그 순간의 a를 결과에 곱해주는 방식이다. 이걸로 O(log b)에 안전하게 지수 계산 가능하다.

---

# dac, python 실전에서는 (a**b)%mod 연산에서는 pow(a,b,mod) 활용
import sys
input=sys.stdin.readline

# pow(a,b,mod) 연산의 직접 구현. 여기서 분할정복이 사용
def mod_pow(a,b,mod):
    result=1
    a%=mod
    while b>0:
        if b%2==1:
            result=(result*a)%mod
        a=(a*a)%mod
        b//=2
    return result

def mod_cal(n,s,mod):
    b=mod_pow(n,mod-2,mod)
    a=s
    return (a*b)%mod

def main():
    m=int(input().strip())
    mod=10**9+7
    result=0
    for _ in range(m):
        n,s=map(int,input().split())
        result=(result+mod_cal(n,s,mod))%mod
    print(result)
    
if __name__=="__main__":
    main()