发现luogu的UI改版后AC以后不能给题目评定难度了……
类似素数筛的一道题，不过是约数。
先顺手写了个暴力做法，TLE定了~
#include<bits/stdc++.h>
using namespace std;
long long n,sum[1000005];
int main()
{
scanf("%d",&n);
for(long long i=1; i<=n; i++)
{
for(long long j=1; j<=i; j++)
if(i%j==0)sum[i]++;
sum[i]+=sum[i-1];
}
printf("%lld",sum[n]);
return 0;
}
O（n²)，20分。
联想埃式素数筛法，我们把循环稍（da）作（liang）改动，
从1到n遍历，把每个数连同他的所有不超过n的倍数所对应的sum数组++：
#include<bits/stdc++.h>
using namespace std;
long long n,sum[1000005];
int main()
{
scanf("%d",&n);
for(long long i=1; i<=n; i++)
for(long long j=i; j<=n; j=j+i)
sum[j]++;
for(long long i=1; i<=n; i++)
sum[i]+=sum[i-1];
printf("%lld ",sum[n]);
return 0;
}
我们就得到了一个O（nloglogn）近似于线性的优化算法~（这nloglogn是我胡扯的，真正的时间复杂度及其推出过程请看luogu题解）
最后数组累加。
原文：https://www.cnblogs.com/yige2019/p/11279892.html