题解 | 区间因数个数之和 #
区间因数个数之和
https://www.nowcoder.com/practice/1ae57482db684866b918c66dbc36cb97?tpId=388&tqId=11297176&channelPut=tracker1
设)
表示区间
所有数的因子个数之和，那么求区间
的因子个数之和为-f(l-1))
如何求
这是暴力循环的代码：
因为区间
中有
个数是
的倍数，即有个数的因子包含
区间中有
个数是
的倍数，即有个数的因子包含
区间中有
个数是的倍数，即有个数的因子包含
.....
int sum = 0;
for(int i = 1; i <= n; i ++){
sum += (n / i);
}
cout << sum << endl;
实际上就是求
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
int work(int x){
int sum = 0;
for(int i = 1; i <= x; i ++){
int l = i, r = (x / (x / i));
sum += (r - l + 1) * (x / i);
i = r;
}
return sum;
}
signed main(){
HelloWorld;
int l, r; cin >> l >> r;
cout << work(r) - work(l - 1) << endl;
return 0;
}
查看3道真题和解析