[백준] 13172 : Σ

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

13172번: Σ

---

- 문제를 정리하자면, 여러 분수들을 통분하고 기약분수로 만드는 것이 어렵기 때문에 특정한 모듈러 연산을 적용한다.

- 이 연산은 a * b'' mod X 로 나타낼 수 있으며, 모든 분수들을 왼쪽의 연산을 적용하고 나온 값에 대해서는 일반적인 모듈러 덧셈, 곱셈 등을 사용해도 결과를 유지할 수 있다.

- 따라서 S 와 N 이 순차적으로 주어질 때, Si 와 Ni 값을 모듈러 연산을 적용하고, 나온 값들을 더해주면 된다.\

- b'' 는 페르마의 소정리에 의해 b^(X-2) mod X 값이 된다고 한다.

- X 가 충분히 큰 수이므로 b 를 X-2 번 제곱하는 것은 불가능하기 때문에, 분할정복을 통해 b의 1승, 2승, 4승, 8승, 16승, ... 을 X 의 비트에 맞게 곱해서 로그X 번으로 결과를 구해준다.

---

#include <iostream>
#define X 1000000007
#define ull unsigned long long

using namespace std;

ull answer, X_ = X-2;
ull M, N, S;

ull reverse(ull N)                          // N 의 모듈러 곱셉에 대한 역원 구하기
{                                           // N^(X-2) 값을 모듈러 X 로 나눈 값
    ull b = 1, digit = 1, temp = N;

    while(digit <= X_)                      // X-2 제곱을 분할하여 곱함
    {
        if(digit & X_) b = (b * temp) % X;  // 비트가 1인 자릿수에서는 b 에 temp 를 곱해줌
        temp = (temp * temp) % X;           // temp 는 계속 제곱해줌으로써 값 유지
        digit = digit << 1;
    }

    return b;
}

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

    cin >> M;
    for(int i = 0 ; i < M ; i++)
    {
        cin >> N >> S;                                  // 문제의 조건에 의해, 기약분수를 구하지 않고
        answer = (answer + (S * reverse(N)) % X) % X;   // 각 모듈러값들을 모듈러 더하기로 구해줌
    }

    cout << answer << endl;
}