[BOJ] 백준 11693 - n^m의 약수의 합

문제 링크

www.acmicpc.net/problem/11693

11693번: n^m의 약수의 합

 

풀이

$p_i$를 소수라 하고, $n$을 소인수 분해하여 $n = p_1^{m_1}p_2^{m_2}...p_k^{m_k}$라 합시다. 이때 약수의 합 $s$는 다음과 같습니다.

$$\begin{eqnarray}s &=& (1+p_1^1+...+p_1^{m_1})(1+p_2^1+...+p_2^{m_2})...(1+p_k^1+...+p_k^{m_k}) \\ &=& \frac{p_1^{m_1+1}-1}{p_1-1}\times \frac{p_2^{m_2+1}-1}{p_2-1}\times ... \times \frac{p_k^{m_k+1}-1}{p_k-1} \end{eqnarray}$$

 

문제 되는 부분이 두 곳 있습니다.

1) $p_i^{m_i}$를 빠르게 계산할 수 있어야 합니다.

2) 결과가 너무 크기 때문에 문제에서 주어진 소수로 모듈러 연산을 해야 하는데, 나눗셈은 모듈러에 대해 닫혀있지 않습니다.

 

1번은 백준 1629 - 곱셈의 해결법을 이용하면 됩니다.

2번은 정수론적 지식이 조금 들어갑니다.

 

우리가 일반적으로 사용하는 나눗셈이라는 게 사실 곱셈의 역원을 곱해주는 것입니다.

즉, 문제를 해결하기 위해 모듈러 체계에서 곱셈의 역원을 구해준 뒤 곱해주면 됩니다.

이에 대해 깔끔하게 정리해둔 글이 있어 설명을 대신하도록 하겠습니다. 모듈러 나눗셈 - OHGYM

 

제 코드에선 확장 유클리드를 이용해서 역원을 구했지만, 문제에서 나누는 수 1,000,000,007이 소수이므로 페르마 소정리를 이용해도 무방합니다.

확장 유클리드를 이용 시 주의할 점이 있습니다. 역원이 음수로 나올 수도 있는데, 이땐 나누는 수를 한 번 더해주시면 됩니다.

정답 코드

#include <bits/stdc++.h>
#define ft first
#define sd second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll MOD = 1'000'000'007LL;

vpll p;
ll n, m;

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

tuple<ll, ll, ll> xGCD(ll a, ll b) {
    if (b == 0) return {a, 1, 0};
    auto[g, x, y] = xGCD(b, a % b);
    return {g, y, x - (a / b) * y};
}

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

    cin >> n >> m;
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            if (!p.empty() && p.back().ft == i) p.back().sd++;
            else p.emplace_back(i, 1);
            n /= i;
        }
    }
    if (n > 1) {
        if (!p.empty() && p.back().ft == n) p.back().sd++;
        else p.emplace_back(n, 1);
    }
    ll ans = 1;
    for (auto &node: p) {
        auto[factor, cnt] = node;
        cnt *= m;
        ll x = (go(factor, cnt + 1) - 1) % MOD;
        ll inv = get<1>(xGCD(factor - 1, MOD));
        if (inv < 0) inv += MOD;
        ans *= x * inv % MOD;
        ans %= MOD;
    }
    cout << ans;
}