97. 约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod =9901; 
ll a,b,ans;
ll qpow(ll x,ll k)
{
    ll res=1;
    x%=mod;
    while(k)
    {
        if(k&1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        k>>=1;
    }
    return res;
}
ll sum(ll p,ll k)
{
    if(k==0)
        return 1;
    if(k%2==0)
        return (p%mod*sum(p,k-1)+1)%mod;
    else
        return (1+qpow(p,k/2+1))*sum(p,k/2)%mod;
}
int main()
{
    cin >> a >>b;
    ans=1;
    for(int i=2;i<=a;i++)
    {
        int cnt=0;
        while(a%i==0)
        {
            cnt++;
            a/=i;
        }
        if(cnt)
            ans=ans*sum(i,cnt*b)%mod;
        //cout<<a<<endl;
    }
    if(!a)
        ans=0;
    cout << ans<<endl;
    return 0;
}

Donate