思路:
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; }