題目要求:
給出一個整數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))
問題得到解決
給出一個整數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
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