[C++] 백준 13172 Σ

#include <iostream>
 
long long power(long long lUnder, long long lUp)
{
    long long lAns = 1;
 
    while (lUp) 
    {
        if (lUp % 2 == 1)
        {
            lAns = lAns * lUnder % 1000000007;
        }
 
        lUp /= 2;
        lUnder = lUnder * lUnder % 1000000007;
    }
 
    return lAns;
}
 
int main()
{
    int N = 0;
    std::cin >> N;
    long long answer = 0;
 
    for (int i = 0; i < N; ++i)
    {
        int Ni = 0;
        int Si = 0;
        std::cin >> Si >> Ni;
 
        answer += (Ni * (power(Si, 1000000007 - 2))) % 1000000007;
    }
 
    std::cout << answer % 1000000007;
 
    return 0;
}

 

문제가 진짜 정말 너무 길었습니다. 서론이 너무 길어서 본론을 찾기가 어려웠는데...

본론은 딱 

 

소수 모듈러에서만 성립하는 페르마의 소정리에 의해 b의X - 1승 ≡ 1 (mod X)가 성립하기에,
b의X - 2승 ≡ b의 -1승 (mod X) 역시 성립함을 알 수 있다.

이 문장이었습니다. a * b의 -1승의 값을 구하기 위해서 X값이 1,000,000,007이기 때문에  b의-1승 = b의X -2승 값인

b의1,000,000,007 - 2승를 구하라는 말이었는데 N의 100승은 N의2승의 50승과 같은 말이기 때문에 계속해서 반으로 나누는 분할제곱을 이용해서 풀었습니다.