[백준] Σ

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

13172번: Σ

우선 문제부터 요약하면, 

 

기약 분수들을 여러개 더하게 되면 통분 등으로 인해 분모등이 원하는 범위 안에서 유지되도록 관리하기가 어렵습니다. 그래서 페르마 소정리를 이용한 역원을 통해 다르게 표현하여 좀더 간단하게 더하려고 하는데, 이렇게 다르게 표현한 것들을 더한 결과를 구하는 문제입니다.

 

실제로 문제를 한번 읽어보는 것이 정확합니다. 사실 수학적인 지식 보다는 문제에서 무엇을 우리에게 구하라고 이야기하는 지만 정확하게 파악하면 되는 문제입니다. 

 

<Solution>

문제에서의 변형은 페르마 소정리를 통한 역원을 구해야 하는데, 사용중인 P(소수)의 값이 굉장히 크므로, 거듭 제곱 계산을 일일히 하지 않고, 분할정복을 이용한 거듭제곱을 사용하여 구합니다. 

 

이렇게 역원을 구한 다음 문제에서 요구하는대로, 기약분수를 변형 시키고 나서 각각을 더해주는 형태로 구현하면 됩니다.

실제 구현은 아래와 같습니다.

 

#include <iostream>

using namespace std;

int M;
int Ni[10000+10];
int Si[10000+10];

int gcd(int a, int b){
    // return condition
    if(b == 0) return a;
    return gcd(b, a%b);
}

long long fast_exp_with_mod(int k, int e, int p){
    // return condition
    if(e == 0) return 1;

    int q = e/2;
    int r = e%2;

    long long t = fast_exp_with_mod(k, q, p);
    int t_ = (r == 0) ? 1 : k;

    return ((t*t)%p)*t_ % p;
}

// p에 대한 k의 modular inverse
int modular_inverse(int k, int p){
    // 페르마 소정리
    // should return k^(p-2) mod p
    return fast_exp_with_mod(k, p-2, p);
}

int change_ratio(int numerator, int denominator){
    long long mod_inv = modular_inverse(denominator, 1000000007);
    
    return mod_inv*numerator % 1000000007;
}

int main(){

    long long ans = 0;

    cin >> M;
    // get input
    for(int i = 0; i<M; i++){
        cin >> Ni[i] >> Si[i];
    }

    int a,b;
    for(int i = 0; i<M; i++){
        int to_div = gcd(Ni[i], Si[i]);
        b = Ni[i]/to_div;
        a = Si[i]/to_div;

        ans+= change_ratio(a,b);
        ans = ans % 1000000007;
    }
    cout << ans << endl;
    return 0;

}