Sumdiv POJ - 1845

點選打開連結

對于 

有  

是以我們隻需要求出a的所有素因子 然後将幂次乘b 搞幾個二分幂累乘即可

但是注意 如果用等比公式的話需要求逆元 會爆longlong

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define M 9901

ll prime[10010];
int book[10010];
int cnt;

void init()
{
    int i,j;
    for(i=2;i<=10000;i++)
    {
        if(!book[i])
        {
            prime[++cnt]=i;
            for(j=i+i;j<=10000;j+=i)
            {
                book[j]=1;
            }
        }
    }
    return;
}

ll getpow(ll a,ll b)
{
    ll ans;
    ans=1;
    while(b>0)
    {
        if(b%2==1)
        {
            ans=(ans*a)%M;
        }
        a=(a*a)%M;
        b/=2;
    }
    return ans;
}

ll getsum(ll p,ll n)
{
    if(n==0)
    {
        return 1;
    }
    if(n%2==1)
    {
        return (getsum(p,n/2)*(1+getpow(p,n/2+1)))%M;
    }
    else
    {
        return ((getsum(p,n/2-1)*(1+getpow(p,n/2+1)))+getpow(p,n/2))%M;
    }
}

int main()
{
    ll a,b,p,ans;
    int i;
    init();
    scanf("%lld%lld",&a,&b);
    ans=1;
    for(i=1;prime[i]*prime[i]<=a;i++)
    {
        if(a%prime[i]==0)
        {
            p=0;
            while(a%prime[i]==0)
            {
                p++;
                a/=prime[i];
            }
            ans=(ans*getsum(prime[i],b*p))%M;
        }
    }
    if(a!=1)
    {
        ans=(ans*getsum(a,b))%M;
    }
    printf("%lld\n",ans);
    return 0;
}