백준 13172 - Σ

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

문제 요약

$N_{i}, \: S_{i}$가 M개 주어지는데 이들을 $a \times (b^{-1} \mod p)$ (p는 소수)의 형태로 바꾸고 그 합의 모듈러를 구하라.

풀이

문제에서 페르마의 소정리를 사용하라고 했으므로 페르마의 소정리를 통해 $N_{i} \mod p$를 구한 뒤 $S_{i}$를 곱하면 된다.

 

문제의 이름처럼 기대값들을 모두 더하는 것을 잊지 말자.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define mod 1000000007

int m;

ll pomod(ll val, int b)
{
    if (b == 1) return val % mod;
    if (b & 1) return pomod(val, b - 1) * val % mod;
    return pomod(val * val % mod, b / 2);
}

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

    cin >> m;
    ll res = 0;

    for (int i = 0; i < m; ++i)
    {
        ll n, s;
        cin >> n >> s;
        res += s * pomod(n, mod - 2) % mod;
        res %= mod;
    }

    cout << res;
}