【hdu 1999】不可摸数

Problem  Description：

s(n)是正整数n的真因子之和，即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何数m，s(m)都不等于n,则称n为不可摸数.

Input：

包含多组数据，首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。

Output：

如果n是不可摸数，输出yes，否则输出no

Sample  Input：

3
2
5

8

Sample  Output：

yes
yes

no

思路：这道题如果它每输入一次你计算一次的话，会超时，因此需要提前打表， 打完表之后直接判断就行。而且打表的时候也要优化它的时间复杂度，然后判断2到1000内不是不可摸数的标记为1，最后只用判断它的flag是0还是1.不过关于我的这个头文件我有一个问题，#include<bits/stdc++.h>据可靠消息，它是一个万能头文件，可是我用它提交的时候，它提示我编译错误。

My  DaiMa：

//#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int Max=500000;
int main()
{
    int t,n,a[500002]={0},flag[1000]={0};//数组a[n]用来存n的正因子之和，flag[n]用来标记n是否为不可摸数，0的话是，1就不是
    for(int i=1;i<=Max/2;i++)
    {
        for(int j=2;j*i<Max;j++)
            a[j*i]+=i;//i是j*i的因子就加上i
    }
    for(int i=1;i<=Max;i++)
    {
        if(a[i]>=2&&a[i]<=1000)//看2到1000内哪些是不可摸数，哪些不是不可摸数
            flag[a[i]]=1;
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(flag[n]==0)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}