洛谷1593 因子和

直接质因数分解然后等比数列求和，再判一下公比模p为1就好了吧？

#include <algorithm>
#include <iostream>
#include <map>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t mod = 9901;

int_t power(int_t base, int_t index) {
    int_t result = 1;
    const int_t phi = mod - 1;
    if (index < 0) index = (index % phi + phi) % phi;
    while (index) {
        if (index & 1) result = result * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}
std::map<int_t, int_t> factor(int_t n) {
    std::map<int_t, int_t> result;
    for (int_t i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            result[i]++;
            n /= i;
        }
    }
    if (n != 1) result[n]++;
    return result;
}
int main() {
    int_t a, b;
    cin >> a >> b;
    auto primes = factor(a);
    int_t result = 1;
    for (const auto& kvp : primes) {
#ifdef DEBUG
        cout << kvp.first << " " << kvp.second << endl;
        // cout << (power(kvp.first, kvp.second * b % mod + 1) - 1) << endl;
        // cout << result * (kvp.second * b % mod + 1) % mod << endl;
#endif

        if (kvp.first % mod != 1) {
            result = result *
                     (power(kvp.first, kvp.second * b % (mod - 1) + 1) - 1) %
                     mod * (power(kvp.first - 1, -1)) % mod;
        } else {
            result = result * (kvp.second * b % mod + 1) % mod;
        }
    }
    cout << result << endl;
    return 0;
}