hdu 1215 七夕节 筛选法 预处理

七夕节

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15559Accepted Submission(s): 4546

数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.

Input

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

Output

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

这道题 ，以前看到过一次， 还是两个月以前。 那时候还是用了最朴实的方法，用最2逼的方式郁闷着为什么过不了。呵呵。虽然那时候看着这题感觉会和 那个筛选法求素数有点 相似的感觉， 但那时候就只知道有筛选法神奇的名称，所以二逼的放过了这题。 今天是偶然看到此题的。到现在素数筛选是没一点问题了，自以为筛选法也不在话下。所以试了此题。

结果还是悲催的接受了TLE。。

下面是我TLE的代码。

#include<stdio.h>
#include<math.h>
#define MAXN 500000
int a[MAXN];
int main()
{
    int n,t,i,j,sum;
    while(scanf("%d",&n)!=EOF)
    {
          while(n--)
          {
                    sum=0;
               scanf("%d",&t);
               for(i=2;i<=sqrt(t);i++)    //数组下标  表示数值。数组值赋为1 代表可能是真因子。
                     a[i]=1;
               for(i=2;i<=sqrt(t);i++)  //这里用筛选法，完全就是按的素数筛选的思路  - - .
               {
                   if(a[i])            //可能是真因子才检验。
                    {
                       if(t%i)         //如果不是真因子 ，那么这个数所有的倍数都不是真因子。
                        {
                           for(j=i;j<=sqrt(t);j+=i)
                           a[j]=0;     
                        }
                     }
               }  
               for(i=2;i<sqrt(t);i++)      //求出测试案例的真因子和。
               {
                   if(a[i])
                      sum+=(i+t/i);
               }
               printf("%d\n",sum+1);
          }
    }
    return 0;
}

其实这种算法我测试了最大的数据500000， 刷一下，很短的时间就算出来了，以为肯定不会TLE了。 但我忽视了 题目要求可能有500000组数据，而我的算法每个测试数据都得筛选一次、500000万组数据 。。。 哥顿时凌乱了。

这让我想到了 前两天刚看过的 预处理。虽然看过，但这是我第一次用预处理，怎么预处理还是让我想了很久。

最后当然还是AC了 。时间46ms ^ ^.

代码如下。

#include<stdio.h>
#include<math.h>
#define MAXN 500000+10
int a[MAXN];
int main()
{
    int n,t,i,j,sum;
    while(scanf("%d",&n)!=EOF)             //先预处理。  此题的收获。
    {
               sum=0;
               for(i=2;i<=MAXN;i++)
                     a[i]=0;
               for(i=2;i<=MAXN;i++)        //将所有数据的真因子之和都一次求出来。
                  for(j=i+i;j<=MAXN;j+=i)  //a[j] 都有i这个因数。所以 都加上i；
                      a[j]+=i;
               while(n--)
               {
                         scanf("%d",&t);
                         printf("%d\n",a[t]+1);
               }
    }
    return 0;
}