题目链接(https://ac.nowcoder.com/acm/problem/14682)
题意简述
给个n,求1到n的所有数的约数个数的和~(n<100000000)
分析
说明
样例解释:
1有1个约数1
2有2个约数1,2
3有2个约数1,3
讲解:
正常想法是用一个双重循环对每个数的约数查找,发现是约束则加1,但这样简单的想法会The Time Limited,所以这要使用数论中的知识了。
可以这样理解:
1~n的约数中都有1,即是1的倍数的数都有约数1;(约数1出现n次)
1~n中是2的倍数的数都有约数2;(约数2出现n/2次)
1~n中是3的倍数的数都有约数3;(约数3出现n/3次)
...
1~n中是n的倍数的数都有约数n;(约数n出现1次)
所以1~n的所有数的约数个数的和为sum(约数)=sum(1)+sum(2)+sum(3)+...+sum(n)=n+n/2+n/3+...+1
AC代码
点击查看代码
#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef double long lf;
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
ll sum=0;
cin >> n;
for(int i=1; i<=n; i++)
{
sum+=n/i;
}
cout << sum << endl;
return 0;
}