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

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

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

输出格式
输出一个整数，代表 Smod 9901 的值。

数据范围
0≤A,B≤5×10⁷

输入样例：

2 3

输出样例：

15

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

参考答案

#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;

const int mod = 9901;
int A, B;

//保存质因子以及出现的次数
unordered_map<int, int> primes;

//试除法质因子分解
void divide(int n) {
    for(int i = 2; i < n / i; i++) {
        if(n % i == 0) {
            while(n % i == 0) {
                primes[i]++;
                n /= i;
            }
        }
    }
    if(n > 1) {
        primes[n]++;
    }
}

//快速幂
int qmid(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

//p0 + .. + pk-1
int sum(int p, int k) {
    if(k == 1) return 1;  //边界
    if(k % 2 == 0) {  
        return (LL)(qmid(p, k / 2) + 1) * sum(p, k / 2) % mod;
    }
    return (qmid(p, k - 1) + sum(p, k - 1)) % mod;
}

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

    //对A分解质因子
    divide(A);

    int res = 1;
    for(auto it : primes) {
        //p是质因子，k是质因子的次数
        int p = it.first, k = it.second * B;
        // res要乘上每一项, 注意这里是k + 1
        res = (LL)res * sum(p, k + 1) % mod;
    }
    if(!A) res = 0;

    cout << res << endl;

    return 0;
}