这篇博客是从旧博客 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", #);
if(sign[num])
printf("no\n");
else
printf("yes\n");
}
return 0;
}