博客

题意：

给个n，求1到n的所有数的约数个数的和~

分析：

一开始以为是分别求1~n的每个数的约数(因数)个数，再求和。每个数的约数求法是，唯一分解定理，指数＋1的乘积和就是约数个数。但是这样的做法超时了。尝试着打n<1000000的表，超过1000000的部分再单独去计算，还是超时。看了别人提交的代码才发现，正解是应该转换思维，1~n中有i这个因子的数有n/i个。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		ans+=n/i;
	}
	printf("%d\n",ans);
	return 0;
}

后来发现还可以再加速：

遇到相同n/i值直接累加并跳过

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,d,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i=n/d+1){
		d=n/i;
		ans+=d*(n/d-i+1);
	}
	printf("%lld\n",ans);
	return 0;
}