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

https://www.acmicpc.net/problem/13172

 

이 문제의 핵심을 정리하면 아래와 같다.

 

기약분수 a/b를 다음과 같이 하나의 정수로 표현할 수 있다. 

 

이 때 X는 1,000,000,007과 같은 큰 소수이다.

b^(-1)은 b의 모듈러 곱셈에 대한 역원인데, 다음과 같이 계산할 수 있다. 

 

이 정도만 알면 문제를 풀 수 있다.

 

이제 구체적으로 어떻게 구현할지 생각해보자.

한 줄에 분모와 분자 순서대로 한 쌍의 분수가 들어온다. 각 분수에 대해 a * b^(-1) mod X 를 구하면 된다. 그리고 모든 값들을 마치 확률을 더하듯 그냥 더해주면 된다. 

 

내가 헷갈렸던 점은 기약분수 a/b에 대해서 저렇게 계산해야 된다고 하길래 들어온 분모와 분자에 대해서 우선 기약분수 형태로 만들어줘야 하나 했었다. 그런데 굳이 그런 처리는 안 해주어도 된다. 

(그리고 분모 분자 순서 반대로 받아서 20분 삽질함...)

 

그래서 분할 정복으로 거듭 제곱하는 함수 하나만 구현해주고 mod 주의해서 계산만 하면 끝~~

 

#include <iostream>
#include <vector>
using namespace std;

int MOD = 1000000007;

long long sq(long long x, long long n) {
    if (n == 0) return 1;
    long long tmp = sq(x , n / 2) % MOD;
    if (n % 2 == 0) return (tmp * tmp) % MOD;
    else return (((tmp * tmp) % MOD) * x) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m;
    cin >> m;

    int ans = 0;

    for (int i = 0; i < m; i++) {
        long long a, b;
        cin >> b >> a;

        int tmp = (a * sq(b, MOD - 2)) % MOD;
        ans = (ans + tmp) % MOD;
    }

    cout << ans << '\n';
}

(AC)