[백준 13172] Σ [C]

백준 - 13172

---

풀이

지문이 어마무시하게 길면서 Fermat’s little theorem에 대해 설명이 친절한 문제이다. 요점은 다음과 같다.

• M개의 N과 S에 대해 S*N^(MOD-2)의 합들을 MOD로 나눈 나머지를 구하면 된다.

단, N^(MOD-2)를 구하는 과정에서 수가 너무 커지므로 중간과정마다 MOD로 나누어줘야 한다.

---

소스코드

#include <stdio.h>
const int MOD = 1e9+7;
int main(){
    long long sum = 0, N;
    int M, S;
    scanf("%d", &M);
    while (M--){
        scanf("%d %d", &N, &S);

        long long temp = 1, k = MOD-2;
        while (k){
            if (k & 1) temp = temp*N %MOD;
            k >>= 1;
            N = N*N %MOD;
        }
        sum = (sum + S*temp) %MOD;
    }
    printf("%lld", sum);
}

---

출처 및 참고자료

13172번: Σ

페르마의 소정리 - 위키백과, 우리 모두의 백과사전