随笔 - 147  文章 - 71  trackbacks - 0
<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

我的其它Blog：
www.cppblog.com/dreamangel/
blog.csdn.net/fjnu_angel/

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜

zoj2095（Divisor Summation）
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 飞翔天使 阅读(461) 评论(0)  编辑  收藏 所属分类: zoj

只有注册用户登录后才能发表评论。
网站导航:
 
Copyright ©2024 飞翔天使 Powered by: 博客园 模板提供：沪江博客