[백준][C++] 13172: Σ

문제

풀이

위의 식을 구하는 것이 문제의 답이다. 페르마의 소정리에 의해 밑의 식이 성립한다.

페르마의 소정리

즉 b^(-1) (mod X)는 b^(X - 2)이므로, 이 b^(X - 2)만 구하면 답을 구할 수 있다. 문제에서 X가 1,000,000,007의 큰 수 이므로 일반적인 제곱을 하면 범위 초과가 발생하므로 mod연산과 분할 정복을 이용하여 제곱값을 구한다. 

 

코드

#include <iostream>

const int MOD = 1'000'000'007;

using namespace std;

// a를 b번 곱하고 c로 나눈 값
long long power(long long a, long long b, long long c)
{
    if (b == 0)
    {
        return 1;
    }
    if (b == 1)
    {
        return a % c;
    }

    long long temp = power(a, b / 2, c);
    temp = temp * temp % c;
    
    // b가 짝수 일 경우
    if (b % 2 == 0)
    {
        return temp;
    }
    // b가 홀수 일 경우
    else
    {
        return temp * a % c;
    }
}

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

    int M;
    long long answer = 0;

    cin >> M;

    while (M--)
    {
        long long N, S;
        cin >> N >> S;

        // b^(-1)이 b^(MOD - 2)이므로 
        // b^(MOD - 2)를 구하고 S를 곱해서 MOD연산
        answer += power(N, MOD - 2, MOD) * S % MOD;
    }

    answer %= MOD;
    cout << answer;

    return 0;
}