【筛法思想】HDU 1215—— 七夕节

题目来源：点击打开题目链接

这个题的意思是，给出一个数，求该数所有因数的和。

本来以为是找规律，结果找了半天也没有找到。枚举又显得超时。输入范围中等，10^5，但枚举的次数达到了10^10，显然是不行的。但看了大神的报告，前面的素数筛法其实也是一种思想，排除了明显不可能的情况，利用性质得出结论。

1、每个数都有因数1.

2、每个数的最大因数都不超过他的1/2。

综合以上，我们可以得到成型的筛法，筛法是一种思想，像DP一样。

#include <iostream>using namespace std;int table[500009];void findbig(){for(int i=1;i<=500000;i++)   //所有数都有因子1 table[i]=1;for(int j=2;j<=500000/2;j++)  //250001肯定不是任何500000以内数的因数 {for(int k=j+j;k<=500000;k+=j) // 筛法自加 table[k]+=j;}} int main(){int testcase;cin>>testcase;findbig();    for(int i=0;i<testcase;i++)    {    int temp;    cin>>temp;    cout<<table[temp]<<endl;    }return 0;}