[BOJ] 백준 13172 - Σ

문제 링크

www.acmicpc.net/problem/13172

13172번: Σ

 

풀이

이번에 새로 solved.ac 클래스 4에 추가된 문제입니다.

페르마 소정리와 모듈러 역원에 대해 친절하게 설명해줍니다. 정말 교육적인 문제예요..

 

이제 문제는 $b^{x-2}$를 구하는 데 있습니다. $x$가 매우 크기 때문에 거듭제곱을 효율적으로 해야 합니다.

백준 1629 - 곱셈 문제와 같은 방식으로 거듭제곱을 빠르게 구해주도록 합시다.

 

 

정답 코드

#include <bits/stdc++.h>
#define TEST int _tt; cin >> _tt; while(_tt--)
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

ll n, s;

ll go(ll x, ll k) {
    if (k == 1) return x;
    if (k & 1) return x * go(x, k - 1) % MOD;
    ll res = go(x, k / 2);
    return res * res % MOD;
}

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

    ll ans = 0;
    TEST {
        cin >> n >> s;
        ll g = gcd(n, s);
        s /= g;
        n /= g;
        ll inv = go(n, MOD - 2);
        ans += s * inv % MOD;
        ans %= MOD;
    };
    cout << ans;
}