HDU - 1999 不可摸数，快速求因子和

题意：定义s[m]为m内的因子的和，给定一个n，判断是否有s[m]==n,若没有，则是不可摸数。

思路：首先要打表求出s[m]的值，标记这些出现过的值。

打表求因子和：

    for(int i=1;i<=500000;i++)

        for(int j=i*2;j<1000000;j+=i)

            sum[j]+=i;//找到j的因子和，j的因子是i

AC代码：

#include<stdio.h>

#include<string.h>

int sum[1000100],a[1010];

int main()

{

    memset(sum,0,sizeof(sum));

    memset(a,0,sizeof(a));

    for(int i=1;i<=500000;i++)

        for(int j=i*2;j<1000000;j+=i)

            sum[j]+=i;//找到j的因子和

    for(int i=2;i<1000000;i++)

        if(sum[i]<=1000)

            a[sum[i]]=1;

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        if(!a[n])

            printf("yes\n");

        else printf("no\n");

    }

    return 0;

}

巴特西

HDU - 1999 不可摸数，快速求因子和

最新文章

热门文章