poj1845

来源:互联网 发布:淘宝联盟pid在哪里 编辑:IT博客网 时间:2019/12/06 10:50
/*(1) 整数的唯一分解定理:任意正整数都有且只有一种方式写出其素因子的乘积表达式。A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)   其中pi均为素数2) 约数和公式:对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)有A的所有因子之和为S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)3)   同余模公式:(a+b)%m=(a%m+b%m)%m(a*b)%m=(a%m*b%m)%m  所以和P :sum = [1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...* [1+pn+pn^2+...+pn^(an*B)].   当n为奇数是有偶数项    则:s=(1+p+....p^(n/2) )*(1+p^(n/2+1) );    当n为奇数时       s=(1+p+....p^(n/2-1) )*(1+p^(n/2+1) )+p^(n/2);*/#include<stdio.h>#include<string.h>#include<math.h>const long long   maxn=50000000+10;const long long   mod=9901;long long power(long long p,long long n)//反复平方法求(p^n)%mod{     long long sq=1;     while(n>0)     {         if(n%2==0) p=(p*p)%mod;        else        {            sq=(sq*p)%mod;            p=(p*p)%mod;        }         n=n/2;    }    return sq;}/*long long power(long long  p,long long  n){    long long  sq=1;    while(n>0)    {        if(n%2)            sq=(sq*p)%mod;        n/=2;        p=p*p%mod;    }    return sq;}*/long long sum(long long p,long long n)//求因子和{    if(n==0) return 1;    if(n%2) return sum(p,n/2)*(1+power(p,n/2+1))%mod;    else return sum(p,n/2-1)*(1+power(p,n/2+1))%mod+power(p,n/2)%mod;}long long p[maxn],n[maxn];int main(){    long long  i,a,b;    while(scanf("%lld%lld",&a,&b)!=EOF)    {        int  k=0;        for(i=2;i*i<=a;)        {            if(a%i==0)            {                p[k]=i;                n[k]=0;                while(a%i==0)                {                    n[k]++;                    a=a/i;                }                k++;            }            if(i==2) i++;            else i=i+2;        }        if(a!=1)        {            p[k]=a;            n[k]=1;            k++;        }        long long ans=1;        for(i=0;i<k;i++)        ans=(ans*sum(p[i],n[i]*b)%mod)%mod;        printf("%lld\n",ans);    }    return 0;}