[백준 13172번] Σ (C++)

문제링크 : https://www.acmicpc.net/problem/13172

13172번: Σ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000007;
int M, N, S;

ll func(ll a, ll b) //분할 거듭제곱
{
    ll tmp = 1;
    while(b)
    {
        if(b%2) tmp = tmp * a % MOD; //홀수
        a = a * a % MOD; //짝수
        b /= 2;
    }
    return tmp;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int M;
    ll result = 0;
    cin >> M;
    for(int i=0; i<M; i++)
    {
        cin >> N >> S; 
        result += (S * func(N, MOD-2)) % MOD; // a * b^(MOD-2) 
    }
    cout << result % MOD;

    return 0;
}

지문이 굉장히 많고 복잡한 문제이다.

지문을 읽고 확실히 이해하는 것만으로도 어렵지만, 막상 문제 푸는 것 자체는 식이 다 나와있어서 그렇게 어렵지 않다.

 

기본적으로 우리가 구해야하는 식은 a × b^(-1) mod X 이다. (X = 1000000007) [a=모든 면의 합, b=해당 면]

이후 지문을 읽어보면 b-1 × b ≡ 1(mod X)인데, 페르마의 소정리에 의해  b^(X - 2) ≡ b^(-1) (mod X) 인 것을 알 수 있다.

따라서 a × b-1 mod X 라는 식은 a x b^(X-2)인 것을 최종적으로 알 수 있다.

 

X의 값이 1000000007로 굉장히 크기 때문에 범위를 long long으로 선언하는 것은 물론, 분할정복을 이용한 거듭제곱을 통해 시간복잡도를 줄여준다.

 

그리고 주의해야하는 것은 각 계산마다 꼭 % MOD를 통해 모듈러 계산을 해주어야 하며 이는 출력시 결과값에도 마찬가지이다.