约数之和

https://www.acwing.com/problem/content/99/

思路：(参考自https://www.luogu.com/article/0gkx6p64)

• 算数基本定理：$A = p_1^{q_1} \times p_2^{q_2} \times \cdots \times p_n^{q_n}$，则$A^B = p_1^{B \cdot q_1} \times p_2^{B \cdot q_2} \times \cdots \times p_n^{B \cdot q_n}$

• 约数和定理：$Sum = (p_1^0 + p_1^1 + … + p_1^{B \cdot q_1})(p_2^0 + p_2^1 + … + p_2^{B \cdot q_2})…(p_n^0 + p_n^1 + … + p_n^{B \cdot q_n})$

定义函数sum(p, k)，计算$\sum_{i = 0}^kp_i$:

1. k = 0 时，返回 1

2. k 为奇数时，sum(p, k)

$=p^0 + p^1 + p^2 + \cdots + p^k$

$= (p^0 + p^1 + p^2 + \cdots + p^{\frac{k-1}{2}}) + p^{\frac{k+1}{2}} \times (p^0 + p^1 + p^2 + \cdots + p^{\frac{k-1}{2}})$

$= (1 + p^{\frac{k+1}{2}}) \times (p^0 + p^1 + p^2 + \cdots + p^{\frac{k-1}{2}})$

$= (1 + p^{\frac{k+1}{2}}) \times sum(p, \frac{k -1 }{2})$

1. k 为偶数时，sum(p, k)

$=(p^0 + p^1 + p^2 + \cdots + p^{k - 1} )+ p^k$

$= sum(p, k - 1) + p^k$

$= (1 + p^{\frac{(k-1)+1}{2}}) \times sum(p, \frac{(k-1) - 1}{2}) + p^k$

$= (1 + p^{\frac{k}{2}}) \times sum(p, \frac{k}{2} - 1) + p^k$

ac代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 9901;

int a, b;

int ksm(int a, int b) {
    int res = 1;
    while(b > 0){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int sum(int p, int k){ // 计算(p^0 + p^1 + p^2 + ... + p^k)
    if(k == 0) return 1;
    else if(k % 2) return (1 + ksm(p, k / 2 + 1)) % MOD * sum(p, k / 2) % MOD;
    else return ((1 + ksm(p, k / 2)) % MOD * sum(p, k / 2 - 1) % MOD + ksm(p, k)) % MOD;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> a >> b;
    if(a == 0){
        cout << 0 << '\n';
        return 0;
    }
    map<int, int> prime;
    for(int i = 2; i * i <= a; i ++){
        while(a % i == 0){
            prime[i] ++;
            a /= i;
        }
    }
    if(a > 1) prime[a] ++;
    int res = 1;
    for(auto x : prime){
        int k = x.second * b;
        res = res * sum(x.first, k) % MOD;
    }
    cout << res << '\n';
    return 0;
}