题目要求：
给出一个整数A，求它的B次幂的所有因数的和
（0 <= A,B <= 50000000）
样例：A＝2，B＝3，则答案是1+2+4+8=15
算法：
看到数据范围巨大，硬搞是不成的
根据唯一分解定理，A可以分解成一系列质数的幂的形式：
A=p1^a1 * P2^a2.....*Pn^an
（P1，P2……是质数）
所以，A^B=p1^(a1*B) * P2*(a2*B).....Pn^(an*B)
然后，A^B的因数，设某个因数为C，则C可以表示成
C＝p1^c1 * p2^c2……* pn^cn
其中0<=ci<=ai＊B
这样一来，给所有因数求和，就相当给所有形如C的数求和
接下来通过合并同类项，得到一个简洁的形式
sum＝（1+p1+p1^2..+p1^(a1*B)）(1+p2+p2^2...+p2^(a2*b)).....(1+pn+pn^2+....+pn^(an*B))
分别把每项中的等比数列求和算出相乘即可
这道题还有一个小Trick：
为了避免高精度计算，答案需要Mod9901输出，但是这导致直接应用（p^(n+1)-1）/(p-1)的公式进行等比数列求和行不通
因为p－1和9901不见得就互素，经查阅资料，得到了一个基于二分法的方法：
1+p1+p1^2+....+p1^n=p1^(n/2)*(1+p1+.....+p1^(n/2-1))
问题得到解决
1 import java.util.*;
2
3
4 public class Main {
5
6 static long modPow(long a,long n)
7 {
8 long MOD=9901;
9 if (n==1) return a%MOD;
10 long tmp=modPow(a,n>>1);
11 tmp=tmp*tmp%MOD;
12 if ((n&1)==1) tmp=tmp*a%MOD;
13 return tmp;
14 }
15
16 static long myPow(long a,long n)
17 {
18 if (n==0) return 1;
19 long ans=modPow(a,(n>>1)+1);
20 ans=(ans+1)%9901;
21 if ((n&1)==1)
22 ans=ans*myPow(a,n>>1)%9901;
23 else
24 {
25 ans=ans*myPow(a,(n-1)>>1)%9901;
26 ans=ans+modPow(a,n>>1);
27 }
28 return ans%9901;
29 }
30
31 public static void main(String[] args) {
32 Scanner cin=new Scanner(System.in);
33 long a=cin.nextLong();
34 long b=cin.nextLong();
35 long ans=1;
36 for (long i=2;i*i<=a;i++)
37 if (a%i==0)
38 {
39 long pow=0;
40 while (a%i==0)
41 {
42 a/=i;
43 pow++;
44 }
45 pow*=b;
46 ans=ans*myPow(i,pow)%9901;
47 }
48 if (a!=1)
49 ans=ans*myPow(a,b)%9901;
50 System.out.println((ans+9901)%9901);
51 }
52 }
53