POJ 1845 Sumdiv 求幂级数的因子和+二分

Description

Input

Output

Sample Input

2 3

Sample Output

15

Hint

Source

1 + p + p^2 + p^3 +...+ p^n

 = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))

 = (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

如：1 + p + p^2 + p^3 + p^4 + p^5 = (1 + p + p^2) * (1 + p^3)

1 + p + p^2 + p^3 +...+ p^n

 = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)
 = (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);

如：1 + p + p^2 + p^3 + p^4 = (1 + p) * (1 + p^3) + p^2

//396K	0MS
#include<stdio.h>
#include<string.h>
#include<math.h>
#define LL long long
#define N 50010
#define M 9901
LL s[N][2],len;
long long multi(long long a,long long b,long long m)//a*b%m
{
    long long ret=0;
    while(b>0)
    {
        if(b&1)ret=(ret+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return ret;
}
long long quick_mod(long long a,long long b,long long m)//a^b%m
{
    long long ans=1;
    a%=m;
    while(b)
    {
        if(b&1)
        {
            ans=multi(ans,a,m);
            b--;
        }
        b/=2;
        a=multi(a,a,m);
    }
    return ans;
}

long long get(long long n)  //S[i][0]代表第i个素数,S[i][1]代表第i个素数的个数
{
    len=0;
    for(long long i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            s[len][0]=i;s[len][1]=0;
            do{n/=i;s[len][1]++;}while(n%i==0);
            len++;
        }
    }
    if(n>1){s[len][0]=n;s[len++][1]=1;}
}
LL solve(LL p,LL a)
{
    LL count=0;
    if(!a)return 1;
    if(a&1)
    {
        LL ans=solve(p,a/2)%M;
        count=(ans+quick_mod(p,a/2+1,M)*ans%M)%M;
        return count;
    }
    else
    {
        LL ans=solve(p,a/2-1)%M;
        count=(ans+quick_mod(p,a/2,M)*(1+(p*ans)%M))%M;
        return count;
    }
    return count;
}
int main()
{
    LL a,b,ans;
    while(scanf("%I64d%I64d",&a,&b)!=EOF)
    {
        ans=1;
        get(a);
        for(LL i=0;i<len;i++)
            ans=(ans*solve(s[i][0],s[i][1]*b)%M)%M;
        printf("%I64d\n",ans);
    }
    return 0;
}