随笔 - 147  文章 - 71  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(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 飞翔天使 阅读(466) 评论(0)  编辑  收藏 所属分类: zoj

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


网站导航: