POJ 1845 Sumdiv

Sol：求A^B所有约数和% MOD的结果。

根据唯一分解定理将A进行因式分解就ok.

等比数列通过奇偶性的判断处理下就行了。

A^B=p1^(a1*B)*p2^(a2*B)*...*pn^(an*B);

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int MOD = 9901; const int maxn = 10000; int prime[maxn+1]; void getPrime() { memset(prime,0,sizeof(prime)); for(int i=2;i<=maxn;i++) { if(!prime[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++) { prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } long long factor[100][2]; int fatCnt; int getFactors(long long x) { fatCnt=0; long long tmp=x; for(int i=1;prime[i]<=tmp/prime[i];i++) { factor[fatCnt][1]=0; if(tmp%prime[i]==0) { factor[fatCnt][0]=prime[i]; while(tmp%prime[i]==0) { factor[fatCnt][1]++; tmp/=prime[i]; } fatCnt++; } } if(tmp!=1) { factor[fatCnt][0]=tmp; factor[fatCnt++][1]=1; } return fatCnt; } long long pow_m(long long a,long long n) { long long ret=1; long long tmp=a%MOD; while(n) { if(n&1) ret=(ret*tmp)%MOD; tmp=tmp*tmp%MOD; n>>=1; } return ret; } //计算a+P+P^2+....+P^N long long sum(long long p,long long n) { if(p==0) return 0; if(n==0) return 1; if(n&1) return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2)%MOD)%MOD; else return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2-1)+pow_m(p,n/2)%MOD)%MOD; } long long solve(long long A,long long B) { getFactors(A); long long ans=1; for(int i=0;i