[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
题目要求:
给出一个整数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==1return 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==0return 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 


posted on 2010-02-22 17:42 sweetsc 阅读(1373) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: