发现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; } AC我们就得到了一个O（nloglogn）近似于线性的优化算法~（这nloglogn是我胡扯的，真正的时间复杂度及其推出过程请看luogu题解）
最后数组累加。
转载于:https://www.cnblogs.com/yige2019/p/11279892.html
相关资源：JAVA上百实例源码以及开源项目