AcWing-97-约数之和

问题

假设现在有两个自然数A和B，S是$A^B$的所有约数之和。

请你求出 S mod 9901 的值是多少。

输入格式

在一行中输入用空格隔开的两个整数A和B。

输出格式

输出一个整数，代表 S mod 9901 的值。

数据范围

0≤A, B≤5×$10^7$

输入样例：

2 3

输出样例：

15

注意: A和B不会同时为0。

思路

对A分解质因数：$A=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*...*p_n^{k_n}$

则：A的约数个数为$(k_1+1)*(k_2+1)*...*(k_n+1)$个

可知，A的约数和为：$(p_1^0+p_1^1+...+p_1^{k_1})*(p_2^0+p_2^1+...+p_2^{k_2})*...*(p_n^0+p_n^1+...+p_n^{k_n})$

从而有：$A^B=p_1^{k_1*B}*p_2^{k_2*B}*p_3^{k_3*B}*...*p_n^{k_n*B}$

故$A^B$的约数和为：$(p_1^0+p_1^1+...+p_1^{k_1*B})*(p_2^0+p_2^1+...+p_2^{k_2*B})*...*(p_n^0+p_n^1+...+p_n^{k_n*B})$

则可以先对A进行质因数分解，再使用快速幂进行运算得出结果。

题解

#include<iostream>
#include<vector>

using namespace std;

const int MOD = 9901;

//快速幂
int quick_pow(int a, int n) {
    int s = 1;
    a %= MOD;
    while (n) {
        if (n & 1) s = s * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }

    return s;
}

// 求 p^0+p^1+...+p^k 的和
int sum(int p, int k) {
    if (k == 0) return 1;
    if (k & 1) return (1 + quick_pow(p, k / 2 + 1)) * sum(p, k / 2) % MOD; //k为奇数，则有偶数项，直接折半
    return (p % MOD * sum(p, k - 1) + 1) % MOD; //奇数项，第一项为一，后面的项全部提出p，提出p后其值为sum(p,k-1)
}

// 分解质因数
vector<pair<int, int>> split(int a) {
    vector<pair<int, int>> res;

    int k = 2;
    while (a != 1) {
        if (a % k == 0) {
            pair<int, int> item;
            int cnt = 0;

            do {
                a /= k;
                cnt++;
            } while (a % k == 0);

            item.first = k;
            item.second = cnt;

            res.push_back(item);
        }
        k++;
    }

    return res;
}

int main() {
    int A, B;
    cin >> A >> B;

    if (A == 0) {
        cout << 0 << endl;
        return 0;
    }

    auto sp_res = split(A);
    int ans = 1;
    for (auto item:sp_res) {
        ans = ans * sum(item.first, item.second * B) % MOD;
    }
    cout << ans << endl;

    return 0;
}