思路:
n的范围为 n <= 100000000
暴力显然不行
所以通过计算 1 ~ n 中每个数的 贡献次数(即每个数作为约数的出现次数) 求和即可。
例如 n=3 时 集合为{1,2,3}
此时
3 1 = 3 即为 1 对于集合的贡献次数
3 2 = 1 即为 2 对于集合的贡献次数
3 3 = 1 即为 3 对于集合的贡献次数
从而得出代码
code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++)
m=m+n/i;
cout<<m;
}
京公网安备 11010502036488号