nyoj_478_月老的烦恼（1）

月老的烦恼（1）

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

月老最近遇到了一个很棘手的问题，就是“剩男”“剩女”急速增长，而自己这边又人手不足导致天天都得加班。现在需要你来帮助月老解决这个问题，牵红绳的规则很简单：每个男生都一个编号n（1<=n<=500000）,编号n的因数之和就是要牵线的女生的编号。

如20的因子是：1,2,4,5,10；

输入

输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

输出

对于每组测试数据,请输出一个代表输入编号N男生的另一半的编号.

样例输入

样例输出

上传者

路过这

//自己的代码：

 #include <stdio.h>

 #define MAX 500001

 int s[MAX]={,};

 int main()

 {

     int T;

     int i,j;

     s[]=s[]=s[]=;

     for(j=;j<MAX;j+=)

     {

         s[j]=;

         for(i=;i*i<j;i++)

         if(j%i==)

         s[j]+=(i+j/i);

         if(i*i==j)

         s[j]+=i;

     }

     for(j=;j<MAX;j+=)

     {

         s[j]=;

         for(i=;i*i<j;i+=)

         if(j%i==)

         s[j]+=(i+j/i);

         if(i*i==j)

         s[j]+=i;

     }

     scanf("%d",&T);

     while(T--)

     {

         int n;

         scanf("%d",&n);

         printf("%d\n",s[n]);

     }

     return ;

 }

//网上找的优秀代码

//筛选法不仅可以用来找素数，还可以用来求因子

#include<stdio.h>

#define max 500000

int a[max+]={};

int main()

{

   int t,n,i,j;

   a[]=a[]=;

   for(i=;i<=max/;i++)

   for(j=i+i;j<=max;j+=i)//若i为n的因子，则n必为i的倍数，故以i为步长

   a[j]+=i;

   scanf("%d",&t);

   while(t--)

   {

        scanf("%d",&n);

        printf("%d\n",a[n]);

    }

    return ;

}

巴特西

nyoj_478_月老的烦恼（1）_201312101248

月老的烦恼（1）

最新文章

热门文章