poj 1845 Sumdiv

poj 1845 Sumdiv

題目大意：就是求A^B的因子和。。。。。

思路：

1、對任意的n，可以這麼表示 n=p1^e1*p2^e2*p3*e3*......pn^en 。(p1,p2,p3......pn都為素數)

2、對任意的n的因子和為:(1+e1+e1^2+......+e1^p1)*(1+e2+e2^2+......+e2^p2)*......*(1+en+en^2+......en^p2)

這兒關鍵是如何求等比數列的和。。。。直接看代碼吧。。。。

code：

#include
#include

using namespace std;

typedef __int64 LL;

const int size=10000;
const int mod=9901;

LL sum(LL p,LL n);
LL power(LL p,LL n);

int main()
{
    int A,B;
    int p[size];
    int n[size];
    while(scanf(%d%d,&A,&B)==2)
    {
        int i,k=0;
        for(i=2;i*i<=A;)
        {
            if(A%i==0)
            {
                p[k]=i;
                n[k]=0;
                while((A%i)==1)
                {
                    n[k]++;
                    A/=i;
                }
            }
            if(i==2)
            {
                i++;
            }
            else
            {
                i+=2;
            }
        }
        if(A!=1)
        {
            p[k]=A;
            n[k++]=1;
        }
        int ans=1;
        for(i=0;i0)
    {
        if(n%2) sq=(sq*p)%mod;
        n/=2;
        p=p*p%mod;
    }
    return sq;
}