hdu 1999

╰+攻爆jí腚メ 2022-08-03 15:59 112阅读 0赞

# 不可摸数 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 10126    Accepted Submission(s): 2627**

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

Author

Zhousc@ECJTU

Source

[ECJTU 2008 Spring Contest ][ECJTU 2008 Spring Contest]

要处理出1-1000000的数的因数的和，刚开始的时候处理只处理了1-1000。。，显然漏了很多。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    int a[1000010];
    int b[1010];
    
    int main()
    {
        for(int i=1;i<=500000;i++)
        {
    
            for(int j=i+i;j<=1000000;j+=i)
            {
                a[j]+=i;
            }
        }
        for(int i=1;i<=1000000;i++)
        {
            if(a[i]<=1000)
            {
                b[a[i]]=1;
    
            }
        }
    
        int T=in();
        while(T--)
        {
            int n=in();
            puts(b[n]==0?"yes":"no");
        }
        return 0;
    }

[ECJTU 2008 Spring Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=ECJTU+2008+Spring+Contest&source=1&searchmode=source