題目要求：
給出一個整數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