BOJ 13172 - Σ

18 Feb 2024 in Posts on Random, CPP

“분할 정복을 이용한 거듭 제곱”

• BOJ 13172 - Σ
  • 문제 링크

BOJ 13172 - Σ

문제 링크

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;

ll MOD = 1000000007;
ll M, a, b;

ll np(ll a, ll b) {
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % MOD;
        b /= 2;
        a = a * a % MOD;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>M;
    ll ans = 0;
    for (int i = 0; i < M; i++) 
    {
        cin>>a>>b;
        // b / a = b * a^(1000000007 - 2) % MOD
        ans += (b * (np(a, MOD - 2))) % MOD;
    }
    cout << ans % MOD;
    return 0;
}

• 두손두발 다들었다… 가장 간소하게 이해한 바로는 두 번째로 들어온 수의 1,000,000,005승을 구하는 것이 핵심이고, 분할 정복을 이용해서 구한다.

ll np(ll a, ll b) {
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % MOD;
        b /= 2;
        a = a * a % MOD;
    }
    return ans;
}

• 문제의 본질까지 이해하는 건 무리일 것 같고, 그것을 차치하더라도 분할정복을 이용한 계승 구하기 코드는 매우 유용할 것 같다.