约数之和

AcWing-97-约数之和

分析

见《进阶指南》第17页。

实现

#include <iostream>
using namespace std;

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

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

int main () {
    int a, b;
    while (cin >> a >> b) {
        if (a == 0) {
            cout << 0 << endl;
            continue;
        }
        int n = prime_factorize(a); // a 质因数的个数
        LL res = 1;
        for (int i = 1; i <= n; ++ i)
            res = res * sum(p[i], e[i] * b) % M;
        cout << res << endl;
    }
    return 0;
}