【题目链接】：click here~~
【题目大意】求
其中sum()表示其所有因子和（0=<A,B<=50000000）。
【思路】
二分等比数列求和，我们先把A的质因子分解出来，然后如下（poj讨论区的思路~~）
1+p+p^2+……+p^c=1° odd(c)=true 原式=cal(p,c)={p^[(c+1)>>1)] +1} *cal(p,(c-1)>>1);2° odd(c)=false 原式=cal(p,c)={p^[(c+1)>>1)] +1} *cal(p,(c-1)>>1) +p^c;原理：例如c=3 分成(1+p)+(p^2+p^3)提出p^2，，二分递归。c=4 分成(1+p)+(p^2+p^3)+(p^4)，p^4单独计算。
代码：
/* * Problem: POJ No.1845* Running time: 16MS * Complier: G++ * Author: javaherongwei * Create Time: 17:01 2015/9/22 星期二*/ #include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;#define MODD(a,b) (((a%b)+b)%b)const LL MOD=9901;LL A,B;LL poww(LL a,LL b){LL res=a,ans=1;while(b){if(b&1) ans=res*ans%MOD;res=res*res%MOD;b>>=1;}return ans;}LL solve(LL A,LL B){ ///递归求解等比数列if(B==0)return 1;if(B&1){return (poww(A,((B+1)>>1))%MOD+1)*(solve(A,(B-1)>>1)%MOD);}if(B%2==0){return (poww(A,((B+1)>>1))%MOD+1)*(solve(A,(B-1)>>1)%MOD)+poww(A,B)%MOD;}}int main(){while(~scanf("%lld %lld",&A,&B)){LL ans=1,sum;for(int i=2; i*i<=A; ++i){if(A%i==0){sum=0;while(A%i==0){sum++;A/=i;}ans=ans*solve(i%MOD,B*sum)%MOD;}}if(A>=2) ans=ans*solve(A%MOD,B)%MOD;printf("%lld\n",ans%MOD);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
才能做到人在旅途，感悟人生，享受人生。
