백준 11693번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 1

사진을 클릭하면 문제로 이동합니다.

---

풀이

 역시 문제 날먹은 수학 이번 문제는 정수론 문제이다. 이 문제를 이해하기 위해서는 사전지식이 필요하다. 임의의 자연수 n에 대해 n이 다음과 같이 소인수분해된다고 해보자.

 

 이때 n의 모든 약수의 합은 다음과 같이 나타낼 수 있다.

 

 각 소인수에 대해 등비수열의 합을 구하고, 이 값들의 곱을 구하면 그것이 약수의 합이 된다. 해당 식을 전개하면 결국 n의 모든 약수들이 나오기 때문이다. 또한, 다음 성질이 성립한다는 것을 알 것이다.

 

이로 인해 n^m은 다음과 같이 나타낼 수 있다.

 

이제 이 모든걸 섞어보면 될 것이다. 결국 구해야하는 것은 다음 식이 된다.

 

각 항을 계산하여 곱해주면 된다. 이때 값이 매우 커질 수 있으니 모듈러 연산을 병행해야하고, 지수가 매우 커질 수 있기 때문에 분할정복을이용한 빠른 제곱을 해줘야 한다. 여기까지는 쉬운데, 문제는 분모를 어떻게 처리하느냐이다. 어쨌든 자연수 수열의 곱이기 때문에 값은 자연수이겠지만, 모듈러 연산에서 나눗셈은 따로 처리할 수 없다. 이를 처리하기 위해, 분모의 값의 모듈러 역원을 찾아 정수 곱의 형태로 변환하고, 모듈러 곱연산을 계속 진행해야한다.

 

 

이때 주어진 M은 10^9+7인 소수이기 때문에, 페르마 소정리를 이용해 모듈러 역원을 구할 수 있다.

코드

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
using ll = long long;

ll n, m;
vector<pair<int,int>> fac;

ll fast_pow(ll a, ll b) { // a^b % MOD
    if (b == 1) return a;

    ll tmp = fast_pow(a, b/2) % MOD;
    tmp *= tmp; tmp %= MOD;

    if (b & 1) return (tmp * a) % MOD;
    else return tmp;
}

void sol() {
    ll ans = 1LL;
    for(int i = 2; i * i <= n; i++) {
        fac.emplace_back(i, 0);
        if (n % i == 0) {
            while(n % i == 0) {
                ++fac.rbegin()->second;
                n /= i;
            }
        }
    }
    if (n != 1) fac.emplace_back(n, 1);

    for(auto& [p, e] : fac) {
        ll inv = fast_pow(p-1, MOD-2);
        ans *= ((fast_pow(p, e*m+1) - 1) * inv) % MOD;
        ans %= MOD;
    }

    cout << ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    sol();
}