HDOJ 1999 不可摸数

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1999


标准的筛选法。求出每个数的因子和
然后看因子和是否在1000以内,是的话就证明等于因子和的这个数是不可摸数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;
 
int sum[1000001], sign[1001];
int main()
{
    int nCases, num;
    scanf("%d", &nCases);
    for(int i = 1; i <= 500000; ++i)
        for(int j = 2*i; j <= 1000000; j += i)
            sum[j] += i;
    for(int i = 1; i <= 1000000; ++i)
        if(sum[i] < 1000)
            sign[sum[i]] = 1;
 
    while(nCases--)
    {
        scanf("%d", &num);
        if(sign[num])
            printf("no\n");
        else
            printf("yes\n");
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注