http://poj.org/problem?id=1845
题意：求A^B的所有约数的和再对9901取模；
做了这个学到了N多数学知识；
一：任意一个整数都可以唯一分解成素因子的乘积；A = p1^k1*p2^k2*......*pn^kn;
A先对2不断取模，当A%2==0时，2的次数加1，直到A%2！=0，A再尝试着对3不断取模.....依次进行下去，直到A = 1；
当A本身就是素数时，A^1就是素数本身的分解式（特殊情况，别忘了加判断）；
这样A^B = p1^(k1*B) * p2(k2*B) * .......*pn^(kn*B);
二：一个数用素因子乘积表示后其约数和公式；
A = p1^k1*p2^k2*......*pn^kn；
则 素因子和 sum = (1+p1+p1^2+p1^3+......+p1^k1) * (1+p2+p2^2+p2^3......p2^k2) * ......*(1+pn+pn^1+pn^2+pn^3+.....pn^kn);
三：用二分递归求等比数列前n项和；
求1+ p+p^2+p^3+.......+p^n
若n是奇数，共有偶数项，sum = (1+p+p^2+....+p^n/2)*(1+p^(n/2+1));
若n是偶数，共有奇数项，sum = (1+p+p^2+.....+p^(n/2-1))*(1+p^(n/2+1))+p^n/2;
四：反复平方法求p^n;
ans = 1;
while(n>0)
{
if(n是奇数) ans = ans*p;
n = n/2;
p = p*p;
}
ans = p^n;
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 const int N = 10000; 5 const int mod = 9901; 6 int p[N]; 7 int n[N]; 8 int A,B; 9 10 //将A分解成素因子的积，A = p[0]^n[0]+p[1]^n[1]+....+p[k-1 ]^n[k-1]; 11 int Div(int A) 12 { 13 int k = 0,i; 14 for(i = 2; i*i <= A;) 15 { 16 if(A%i == 0) 17 { 18 n[k] = 0; 19 p[k] = i; 20 while(!(A%i)) 21 { 22 n[k]++; 23 A/=i; 24 } 25 k++; 26 } 27 if(i == 2) 28 i++; 29 else i += 2; 30 } 31 if(A != 1) 32 { 33 p[k] = A; 34 n[k++] = 1; 35 } 36 return k; 37 } 38 39 long long power(long long p,long long n)//用反复平方法计算p^n; 40 { 41 long long sq = 1; 42 while(n>0) 43 { 44 if(n&1) 45 sq = (sq*p)%mod;//若n是奇数，把p乘到sq; 46 n = n/2; 47 p = p*p%mod; 48 } 49 return sq; 50 } 51 52 long long cal(long long p,long long n)//用反复平方法计算1+p+p^2+....p^n; 53 { 54 if(n == 0) 55 return 1; 56 if(n&1)//如果n是奇数 57 return (cal(p,n/2)*(1+power(p,n/2+1)))%mod; 58 else return (cal(p,n/2-1)*(1+power(p,n/2+1))+ power(p,n/2))%mod; 59 } 60 61 int main() 62 { 63 while(~scanf("%d %d",&A,&B)) 64 { 65 int k,i,sum; 66 k = Div(A); 67 68 sum = 1; 69 for(i = 0; i < k; i++) 70 { 71 sum = (sum*(cal(p[i],n[i]*B)%mod))%mod; 72 } 73 printf("%d ",sum); 74 } 75 return 0; 76 }