백준 13172번: Σ (모듈러 역원)

문제링크:13172번: Σ (acmicpc.net)

13172번: Σ

이 문제는 M개의 N면체 주사위를 굴렸을때, 그리고 그 주사위의 모든 면의 수의 합이 S일때 모든 주사위를 굴렸을 때의 기대값을 구하는 문제이다. 각 주사위의 기대값은 간단하게 S/N으로 구할 수 있지만, 여기서 구한 S/N들을 더하는 과정에서 생길 수 있는 오류와 효율적인 방법에 대해 다루는 문제이다. 문제를 처음 읽었을 때에는 모듈러가 무엇인지 잘 몰라서 잘 이해가 안갔는데, 몇번 읽어보니 이해 할 수 있었다.

 

백준의 문제를 풀다 보면 가끔 엄청나게 큰 수를 계산하거나 다룰 때 K로 나누었을때 나머지 (mod K)를 출력하라고 하는 경우가 있다. 엄청나게 큰 수끼리 더하거나 곱하는 경우 컴퓨터가 연산해야 할 숫자와 자릿수가 크게 늘어나게 된다. 예로 각각 100자리수인 A,B를 곱하면 결과는 200자리수의 매우 큰 숫자가 될 것이다. 200자리수의 숫자가 답과 같은지 비교하는 과정에서 시간이 매우 오래 걸리므로 시간을 단축하기 위해 K로 나누었을때의 답을 출력하게 하는 것이다. 그러면 답은 항상 K보다 작은 수가 되기에 훨씬 적은 시간으로도 답이 맞는지 비교 할 수 있다. 또한 이렇게 mod K의 답을 구하는 과정에서 A와 B를 각각 K로 나눈 나머지로 변환하고 계산을 해도 덧셈, 뺼셈, 곱셈은 답에 mod K를 한것과 항상 같게 나온다. 그래서 문제 풀이 과정에서도 큰 수가 나오면 모듈러 연산을 해 주어 풀이 과정에서의 시간도 단축 할 수 있다.

 

그러나 모듈러 연산에서 나눗셈은 덧셈, 뺄셈, 곱셈과 달리 결과값에 모듈러 연산을 한것과 항상 같게 나오지 않는다. 이 문제에서 기대값은 S/N으로 구할 수 있는데, 모듈러 연산에서 나눗셈이 나오게 되면 S * N^-1 mod(X) 형태로 전환하고, 문제에서 설명한 소수 모듈러에서만 적용되는 페르마의 소정리를 이용해 N^-1 mod(X) 를 N^(X-2) (mod(X)) 로 전환하면

S * N^(X-2) mod(X) 가 되고, 이제 나눗셈 형태가 완전히 곱셈으로 바뀌었으니 기존에 하던 모듈러 곱셈을 해주면 된다. 이 문제에서는 소수를 1,000,000,007로 잡았기 때문에 1,000,000,005제곱을 해주어야 한다. 매우 큰 수를 제곱 해야 하므로 분할 정복을 사용한 제곱을 사용한다.

import sys
import math

mod=1000000007
def power(num,exp):
    if exp==0:
        return 1
    if exp==1:
        return num
    else:
        if exp%2==0:
            return power((num*num)%mod,exp//2)%mod
        else:
            return num*power(num,exp-1)%mod
        
M=int(sys.stdin.readline().rstrip())

ans=0

for i in range(M):
    N,S=map(int,sys.stdin.readline().rstrip().split())
    gcd=math.gcd(N,S)
    N=N//gcd
    S=S//gcd
    ans+=(S*power(N,mod-2))%mod
    ans=ans%mod
    
print(ans)

지금까지 백준 문제를 풀어오면서 모듈러에 대한 것을 정확하게 알지 못했다. 사실 대충 모듈러 상의 곱셈, 덧셈, 뺄셈은 전체 결과의 모듈러를 해준 것과 같다는 것은 알고 있었지만 나눗셈의 모듈러 연산은 생각하지 못했었다. 모듈러 연산이 그래도 처리 속도나 큰 수의 계산과 같은 곳에 많이 사용된다고 하니깐 중요한 개념 같다.