[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 閱讀(1469) 評論(0)  編輯  收藏

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 孙吴县| 盖州市| 治多县| 德安县| 阳城县| 高雄县| 当阳市| 宣武区| 衢州市| 渝北区| 永泰县| 崇阳县| 北川| 阿拉善右旗| 饶阳县| 长春市| 安溪县| 田阳县| 石渠县| 蕉岭县| 南江县| 万山特区| 乳源| 马边| 嘉鱼县| 勃利县| 南江县| 梨树县| 营山县| 丹东市| 呈贡县| 浦东新区| 周至县| 漳州市| 宝兴县| 德令哈市| 内丘县| 海盐县| 日照市| 中卫市| 台东县|