poj 1845 Sumdiv(二分再帰的に等比数列＋素数分解を求める)

タイトル:http://poj.org/problem?id=1845
Sumdiv
Time Limit: 1000 MS
 
メモリLimit: 30000 K
Total Submissions: 16348
 
Acceepted: 4075
Description
Consder two natural numbers A and B.Let S be the sum of all natual divisors of A^B.Determine S modulo 9901(the rest of the division of S by 9901)
Input
The only line contains the two naturaal numbers A and B、(0<=A、B<=50000000)separated by blanks.
Output
The only line of the output will contain S modulo 9901.
Sample Input

2 3

Sample Output

15

ベント
2^3=8. 
The natual divisors of 8 are:1,2,4,8.The ir sum is 15. 
15 modulo 9901 is 15(that Shoutput) 
A^Bのすべての因子の和を求めます.A=180=2^2*3*5、B=2を仮定すると、A^B=(2^2*3^2*5)^2=2^4*3^4*5^2、それに対応する因子とは(1+2+……+2)*(1+3+……+3)(+5+5+2)です.このようにする時、私のもとの考えは直接に数式よりも逆元を掛ける方法でやります.しかし、間違えました.どこに問題があるか分かりません.次の文を紹介します.等比式について:

フェマの小定理に関する降冪:

次のコードのために3分間黙祷します.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=9901; //mod     --》    
typedef long long LL;
LL factor[7500][2], sum; //factor         ，   MLE
void resolve(LL x){
    sum=0;
    memset(factor,0,sizeof(factor));
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            factor[sum][0]=i;
            while(x%i==0){
                factor[sum][1]++;
                x/=i;
            }
            sum++;
        }
    }
    if(x>1){
        factor[sum][0]=x;
        factor[sum++][1]=1;
    }
}
LL quick_mod(LL a,LL b){
    LL ans=1,temp=a%mod;
    while(b){
        if(b&1) ans=ans*temp%mod;
        temp=temp*temp%mod;
        b>>=1;
    }
    return ans;
}
LL Extend_Eulid(LL b,LL a) //    d mod
{
    LL x1,x2,x3,y1,y2,y3 ;
    x1=1,x2=0,x3=a,y1=0,y2=1,y3=b ;
    while(y3 && y3!=1)
    {
        LL q=x3/y3 ;
        LL t1,t2,t3 ;
        t1=x1-q*y1,t2=x2-q*y2,t3=x3-q*y3 ;
        x1=y1,x2=y2,x3=y3 ;
        y1=t1,y2=t2,y3=t3 ;
    }
    if(!y3)return -1 ;
    while(y2<0) y2+=mod; //       
    return y2 ;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    LL a,b;
    while(cin>>a>>b){
        if(b==0){  puts("1");  continue;  }
        if(a==0){  puts("0"); continue;   }
        resolve(a);
        LL ans=1;
        for(LL i=0;i<sum;i++){
            factor[i][1]*=b;
            factor[i][1]++;
            LL pow=factor[i][1]; //%(mod-1);
            LL m=(quick_mod(factor[i][0],pow)-1+mod)%mod;
            LL ni=Extend_Eulid(factor[i][0]-1,mod);
            ans=(ans*m%mod)*ni%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}

私は他の人を見ましたが、二分再帰的に等数列を求めます.はい、この方法で.考え方:等比数列の合計、再帰二点:1+p+p^2+…+p^nに対して、nが奇数ならば、ここに偶数項があります.例えば、n=5:S=1+p+p^2+p^3+p^4+p^5=(1+p)+p^2(1+p+2+p^3) n=3:S=1+p+2+p^3=(1+p)+p^2(1+p); 
を取得しました. 
nが偶数なら、ここに奇数の項目があります.例えば、n=4:S=1+p+p^2+p^3+p^4=(1+p)+p^2+p^3(1+p)=(1+p)(1+p)(1+p)n=2:S=1+p+2 
を取得しました.
memory:836 KB,time:16 ms

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=9901; 
typedef long long LL;
LL factor[7500][2], sum;
void resolve(LL x){
    sum=0;
    memset(factor,0,sizeof(factor));
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            factor[sum][0]=i;
            while(x%i==0){
                factor[sum][1]++;
                x/=i;
            }
            sum++;
        }
    }
    if(x>1){
        factor[sum][0]=x;
        factor[sum++][1]=1;
    }
}
LL power(LL a,LL b){
    LL ans=1,temp=a%mod;
    while(b){
        if(b&1) ans=ans*temp%mod;
        temp=temp*temp%mod;
        b>>=1;
    }
    return ans;
}
LL cal(int p,int n){
    if(n==0) return 1;
    if(n&1){//(1+p+p^2+....+p^(n/2))*(1+p^(n/2+1));
         return (1+power(p,n/2+1))*cal(p,n/2)%mod;
    }
    else { //(1+p+p^2+....+p^(n/2-1))*(1+p^(n/2+1))+p^(n/2);
         return (power(p,n/2)+(1+power(p,n/2+1))*cal(p,n/2-1))%mod;
    }
}
int main()
{
    //freopen("cin.txt","r",stdin);
    LL a,b;
    while(cin>>a>>b){
        if(b==0){  puts("1");  continue;  } //0^0=1
        if(a==0){  puts("0"); continue;   }
        resolve(a);
        LL ans=1;
        for(LL i=0;i<sum;i++){
            factor[i][1]*=b;
            ans=ans*cal(factor[i][0],factor[i][1])%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}