隨筆 - 147 
文章 - 71 
trackbacks - 0


           
	

          

          
	
		
          
			
          
	
          
		
          <2025年6月>
          
	
          日一二三四五六
          25262728293031
          1234567
          891011121314
          15161718192021
          22232425262728
          293012345
          

          

          
			



			

          常用鏈接
          


          留言簿(1)
          




		
          隨筆分類(146)
          
		
				
			
	
		
          隨筆檔案(147)
          
		
				
			
	
		
          文章分類(28)
          
		
				
			
	
		
          文章檔案(28)
          
		
				
			
	
		
          喜歡的Blog
          
		
				
			
	




          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評論
	
          



          閱讀排行榜
          



          評論排行榜
          


          		
	

          

          
	
					


          
	
	http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2095
          
          【題意簡述】
          
求約數(shù)和。
          
【分析】
          
暴力求解必然超時。假設(shè)n可以被分解為a*b，則div(n)里肯定包含a+b；只要從1到(int)n^1/2分解為兩約數(shù)的積的形式，然后加上分解出來的約數(shù)，最后再減去本身就是最終的結(jié)果了。

          import java.util.*;
          
          import java.io.*;
          

          
          public class zoj_2095{
          
    
          
              public static void main(String rgs[]) throws Exception
          
              {
          
        BufferedReader stdin           = 
          
                      new BufferedReader(
          
                          new InputStreamReader(System.in));
          
                  int[] a=new int[500001];        
          
                  int i,j,n,t,k=(int)(Math.sqrt(500000));
          
                  for(i=1;i<=k;i++){
          
                      for(j=i;j<=500000/i;j++)
          
                a[i          *j]+=(i+j);    // 分解為兩約數(shù)積，同時在記錄n約數(shù)和的a[n]中加上(i+j)
          
                      a[i*i]-=i;           // 當然別忘了算了兩次的同一個值只有平方數(shù)才有
          
                  }
          
        String line           = stdin.readLine(); 
          
        t           = Integer.parseInt(line);
          
                  for(i=0;i<t;i++){
          
            line           = stdin.readLine();
          
            n           = Integer.parseInt(line);
          
            System.out.println(a[n]          -n);
          
        }
          
    }
          
}
          

	
          posted on 2009-08-28 10:44 飛翔天使 閱讀(472) 評論(0)  編輯  收藏  所屬分類: zoj 
          

          







          
	    
    




          





          


          

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


          

		          		
		
          
		
          			
		
		
		
		
          
		
          
		
		
          
		
          
			網(wǎng)站導航:
		
		
          
		
          
			
		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				
	



          



    







          
        
	




主站蜘蛛池模板：
上栗县|
汕尾市|
米易县|
德州市|
日土县|
德安县|
库车县|
蒙山县|
嘉鱼县|
海原县|
定襄县|
徐汇区|
桐城市|
会同县|
元阳县|
吴堡县|
克拉玛依市|
宜兰市|
井陉县|
西盟|
新晃|
潢川县|
岳阳市|
万安县|
邮箱|
凤山市|
德庆县|
富阳市|
桑日县|
保德县|
会宁县|
郯城县|
叶城县|
介休市|
旺苍县|
和硕县|
台东县|
巴彦淖尔市|
华蓥市|
东丽区|
昌黎县|