莫欺少年穷，修魔之旅在这开始—>算法提高课题解

重要知识：分解质因数，约数和定理

可参考
1. 分解质因数
2. 约数之和

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 9901;

//快速幂，计算res = a ^ b;
int qmi(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;
}

//sum(p, k) = p^0 + p^1 + … + p^(k-1)
int sum(int p,int k)
{
    if(k==1) return 1;
    if(k%2==0) return (1+qmi(p,k/2))*sum(p,k/2)%mod;
    return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main()
{
    int a,b;
    cin>>a>>b;

    //试除法求质因子
    int res=1;
    for(int i=2;i<=a/i;i++)
        if(a%i==0)
        {
            int s=0;
            while(a%i==0) a/=i,s++;
            res=res*sum(i,b*s+1)%mod;
        }

    if(a>1) res=res*sum(a,b+1)%mod;
    if(!a) res=0;

    cout<<res<<endl;

    return 0;
}