数论—约数之和
然后求一个数的约数之和呢
第一步对A继续分解质因数 得到的结果为p1^c1 * p2^c2···pncn (其中p1，p2为A的质因数)
那么A的所有约数的和为(p1^0 + p1^1 + p1^2 + ··· +p1^c1)(p2^0 + p2^1 + p2^2+···+p2^c2)···(pn^0+pn^1+··+pn^cn)
比如12分解质因数后的结果为2^23
12的所有的约数和为(1+2+4)(1+3) = 74=28
12的约数有1 + 2 + 4 + 6 + 3 + 12 = 28
这题也是一样的
我们要先对A^B这个数进行分解质因数
如何对A^B这个数进行分解质因数呢？
我们只要对A分解质因数即可
A分解质因数的结果为p1^c1 * p2^c2···pncn
那么A^B分解质因数的结果为p1^(c1B)p2^(c2B)p3^(c3B)···pn^(cn*B)
然后调用约数之和的公式即可
案例 2^3
对2分解质因数的结果为2^1
2^3分解质因数的结果为2^3
2^3的约数之和为(2^0 + 2^1 + 2^2 +2^3) = 1 + 2 + 4 + 8 = 15

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int Mod = 9901;
const int N = 5e7 + 100;
int A;
int B;
int primes[N]; //质因数
int len;
int num[N]; //质因数的个数

//快速幂
int qmi(int a , int k){
    int res = 1;
    while(k){
        if (k & 1) res = (LL)res * a % Mod;
        k = k >> 1;
        a = (LL)a * a % Mod;
    }//while
    return res;
}
int sum(int p ,int n){  //这个函数用分治法求等比数列
    if (n == 0) return 1;
    if (n % 2){  //n是奇数则应该有偶数个数,可以正好分成左右2部分
        return ((LL)sum(p , (n - 1) / 2) * (1 + qmi(p , (n + 1) / 2))) % Mod;
    }//如果n是偶数，那么n-1就是奇数，先省略掉p^n 那么就变成了sum(p , n - 1) + p^n
    return ((LL)sum(p , n - 1) + qmi(p , n)) % Mod;
}
void get_prime(int x){
    for (int i = 2;i <= x / i;i++){
        if (x % i == 0){ //i为x的一个质因数
            primes[len++] = i;
            int s = 0; //质因数的个数
            while(x % i == 0){ //把x中的i除干净
                x /= i;
                s++;
            }//while
            num[i] = s; //i这个质因数的个数
        }//if
    }//for
    if (x > 1){
        primes[len++] = x;
        num[x] = 1;
    }
}
int main (){
    cin >> A >> B;
    int res = 1;
    get_prime(A);  //先对A进行分解质因数
    /*for (int i = 0;i < len;i++){
        int prime = primes[i];
        int n = num[prime];
        cout << prime << " " << n << endl;
    }*/
    //求A^B的质因数
    for (int i = 0;i < len;i++){
        int prime = primes[i];
        LL n = (LL)num[prime];
        num[prime] = n * B;

    }
    //然后借助公式求约数和
    for (int i = 0;i < len;i++){
        int prime = primes[i]; //质因数
        int n = num[prime];
        //我们需要算一个1+p^1+p^2+··+p^c 这是一个等比数列
        //我们其实只要算sum(p , c/2) 即可 后面的一半可以由前一半得到
        /*if(n % 2){//n是奇数
            for (int j = 0;j <= (n - 1) / 2;j++){ //sum(prime , (n-1)/2)
                add = add + qmi(prime , j) % Mod;  //用快速幂求p^i
            }//for
            //后一半应该是sum(prime , (n-1)/2) * p^[(n+1)/2]
            add = add * (1 + qmi(prime , (n+1) / 2)) % Mod;
        }//if
        else{
            for (int j = 0;j <= n / 2 - 1;j++){
                add = add + qmi(prime , j) % Mod;
            }
            //后一半应该是sum(prime,[(n/2-1)]) * p^(n/2)
            add = add * (1 + qmi(prime , n/2)) % Mod + qmi(prime , n) % Mod;
        }//else*/
        res = (LL)res * sum(prime , n) % Mod;
    }
    if (!A) res = 0;
    cout << res << endl;
    return 0;
}