这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1215
帅选法。。。
上次在博客里写了一篇:
The Sieve of Eratosthens(爱拉托逊斯筛选法)
啥时候把筛选法好好总结下。
代码:
// Atuhor: Tanky Woo
// HDOJ 1215
// Accepted 1215 265MS 2216K 406 B C++ Tanky Woo
#include
#include
using namespace std;
int qixi[500010];
int main()
{
for(int i=0; i<=500000; ++i)
qixi[i] = 1;
for(int i=2; i<=500000; ++i)
for(int j=2; j*i<=500000; ++j)
qixi[i*j] += i;
int nCases, nNum;
cin >> nCases;
while(nCases--)
{
cin >> nNum;
cout << qixi[nNum] << endl;
}
//getchar();
return 0;
}