隨筆 - 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
          
          【題意簡述】
          
求約數和。
          
【分析】
          
暴力求解必然超時。假設n可以被分解為a*b，則div(n)里肯定包含a+b；只要從1到(int)n^1/2分解為兩約數的積的形式，然后加上分解出來的約數，最后再減去本身就是最終的結果了。

          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);    // 分解為兩約數積，同時在記錄n約數和的a[n]中加上(i+j)
          
                      a[i*i]-=i;           // 當然別忘了算了兩次的同一個值只有平方數才有
          
                  }
          
        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 
          

          







          
	    
    




          





          


          

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


          

		          		
		
          
		
          			
		
		
		
		
          
		
          
		
		
          
		
          
			網站導航:
		
		
          
		
          
			
		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				
	



          



    







          
        
	




主站蜘蛛池模板：
海淀区|
阿克苏市|
河南省|
彭泽县|
长沙市|
菏泽市|
广灵县|
乌鲁木齐市|
剑川县|
通河县|
余庆县|
永丰县|
微山县|
若尔盖县|
临沧市|
定西市|
桑植县|
昌邑市|
太康县|
河曲县|
庆云县|
白银市|
中牟县|
古交市|
海宁市|
响水县|
孝感市|
永春县|
青冈县|
河津市|
蓝田县|
肇东市|
明星|
永春县|
洪雅县|
五莲县|
綦江县|
沽源县|
离岛区|
文安县|
扶余县|