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;
#include<stdio.h>
#include<string.h>
#include<math.h>
const int N = ;
const int mod = ;
int p[N];
int n[N];
int A,B; //将A分解成素因子的积，A = p[0]^n[0]+p[1]^n[1]+....+p[k-1 ]^n[k-1];
int Div(int A)
{
int k = ,i;
for(i = ; i*i <= A;)
{
if(A%i == )
{
n[k] = ;
p[k] = i;
while(!(A%i))
{
n[k]++;
A/=i;
}
k++;
}
if(i == )
i++;
else i += ;
}
if(A != )
{
p[k] = A;
n[k++] = ;
}
return k;
} long long power(long long p,long long n)//用反复平方法计算p^n;
{
long long sq = ;
while(n>)
{
if(n&)
sq = (sq*p)%mod;//若n是奇数，把p乘到sq;
n = n/;
p = p*p%mod;
}
return sq;
} long long cal(long long p,long long n)//用反复平方法计算1+p+p^2+....p^n;
{
if(n == )
return ;
if(n&)//如果n是奇数
return (cal(p,n/)*(+power(p,n/+)))%mod;
else return (cal(p,n/-)*(+power(p,n/+))+ power(p,n/))%mod;
} int main()
{
while(~scanf("%d %d",&A,&B))
{
int k,i,sum;
k = Div(A); sum = ;
for(i = ; i < k; i++)
{
sum = (sum*(cal(p[i],n[i]*B)%mod))%mod;
}
printf("%d\n",sum);
}
return ;
}