分治

约数之和

原题链接

#include<iostream>



using namespace std;

const int mod=9901;


int power(int a,int b)
{
    int res=1%mod;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int sum(int p,int c)
{
    if(c==0) return 1;
    if(c%2==0)//c为偶数时
    {
        return (1+power(p,c/2))*sum(p,c/2-1)%mod+power(p,c);
    }
    else //c为奇数时
    {
        return (1+power(p,(c+1)/2))*sum(p,(c-1)/2)%mod;
    }
}

int main()
{
    int A,B;
    cin>>A>>B;
    //先分解质因数
    int res=1;
    for(int i=2;i<=A;i++)
    {
        int s=0;
        while(A%i==0)
        {
            s++;
            A/=i;//其中s表示p1的个数
        }
        if(s)res=res*sum(i,B*s)%mod;//sum(p,c)
    }
    if(!A) res=0;
    cout<<res<<endl;
    return 0;
}