ZOJ 2286 Sum of Divisors

好吧，这其实是一道菜题。


 1#include <cstdio>
 2#include <string>
 3
 4const int MAXN = 1000000;
 5int b[2][3393000];
 6
 7int main ()
 8{
 9    memset ( b, 0, sizeof ( b ) );
10    int i, j;
11    for ( i = 2; i <= 1000000; i ++ )
12        b[0][i] = 1;
13    for ( i = 2; i <= 1000; i ++ )
14    {
15        j = MAXN / i;
16        while ( j > i )
17        {
18            b[0][i * j] += i + j;
19            j --;
20        }
21        b[0][i * i] += i;            
22    }
23    for ( i = 1; i <= 1000000; i ++ )
24    {
25        b[1][b[0][i]] ++;
26    }
27    int sum = 0;
28    for ( i = 0; i < 3393000; i ++ )
29    {
30        sum += b[1][i];
31        b[0][i] = sum;
32    }
33
34    //freopen ( "in.txt", "r", stdin );
35    int N;
36    while ( scanf ( "%d", &N ) != EOF )
37    {
38        if ( N > 3392928 )
39            printf ( "1000000\n" );
40        else
41            printf ( "%d\n", b[0][N] );
42    }
43    return 0;
44}

posted on 2008-02-05 14:19 杜仲当归 阅读(375) 评论(0)  编辑 收藏 引用

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

导航

<2008年2月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜