Hdu1999 不可摸数（求多个数的因子和）

 

 

 

/***************************
	1. i 从1开始，只要是i的倍数，则都 +=i ；
	2.循环结束后，所有数的因子和都算出了
	3.标记这些因子和； 
# 2013-11-21 22:09:44 
# Time: 15MS   Memory: 2212K
# Author: zyh
***************************/ 
#define N 500005
#include<stdio.h>
bool f[1010];
int a[N];

void find()
{
	for(int i=1;i<=N/2;i++)
		for(int j=i+i; j<=N; j+=i) //j是i的倍数，即i是j的因子 
			a[j] += i;
	for(int j=1;j<=N;j++)
		if(a[j]<=1000) f[a[j]] = 1;	
} 
int main()
{
	int t,n,i,ans;
	find();
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%s\n",f[n]?"no":"yes");
	}
	return 0; 
}