蒟蒻求助数学题

40pts,WA on #1~10

按算法竞赛进阶指南的分治思路去做的。。。

code:

#include<bits/stdc++.h>
#define ll long long
#define mod 9901
using namespace std;

ll qpow(ll x,ll p)
{
    ll ans=1;
    while(p)
    {
        if(p&1) ans=ans*x%mod;
        else x=x*x%mod;
        p>>=1;
    }
    return ans;
}

ll sum(ll p,ll c)
{
    if(c==0) return 1;
    if(c==1) return p+1;
    if(c&1) return (1+qpow(p,(c+1)/2))*sum(p,(c-1)/2)%mod;
    return ((1+qpow(p,c/2))*sum(p,c/2-1)+qpow(p,c))%mod;
}

int main()
{
    ll a,b,ans=1,i=2,x=0;
    cin>>a>>b;
    while(a>1)
    {
        if(a%i==0)
        {
            x++;
            a/=i;
        }
        else
        {
            ans=ans*sum(i,b*x)%mod;
            i++;
            x=0;
        }
    }
    ans=ans*sum(i,b*x)%mod;
    i++;
    x=0;
    cout<<ans;
    return 0;
}