约数之和

AcWing-97-约数之和

分析

见《进阶指南》第152页。

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 20, M = 9901;
int idx, p[N], e[N];

void prime_factorize (int x) {
    for (int i = 2; i <= x / i; ++ i) {
        if (x % i == 0) {
            int j = 0;
            while (x % i == 0) {
                ++ j;
                x /= i;
            }
            p[++ idx] = i;
            e[idx] = j;
        }
    }
    if (x > 1) {
        p[++ idx] = x;
        e[idx] = 1;
    }
}
int power (int a, LL b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}

int main () {
    int a, b;
    cin >> a >> b;

    if (a == 0) {
        cout << 0 << endl;
        return 0;
    }
    prime_factorize(a);
    int res = 1;
    for (int i = 1; i <= idx; ++ i) {
        if ((p[i] - 1) % M == 0) {
            res = ((LL)b * e[i] + 1) % M * res % M;
            continue;
        }
        int x = power(p[i], (LL)b * e[i] + 1, M); // 分子
        x = (x - 1 + M) % M;
        int y = p[i] - 1; // 分母
        y = power(y, M - 2, M);
        res = (LL)res * x % M * y % M;
    }
    cout << res << endl;
    return 0;
}