Blog·Tanky WooABOUTRSS

HDOJ 1999 不可摸数

15 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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


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

#include 
#include 
#include 
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;
}