题解 | 区间因数个数之和 #

$[模板+数论分块]$

设 $f(x)$ 表示区间 $[1,x]$ 所有数的因子个数之和，那么求区间 $[l,r]$ 的因子个数之和为 $f(r)-f(l-1)$

如何求 $f(x)$

这是暴力循环的代码：

因为区间 $[1,n]$ 中有 $\frac{n}{1}$ 个数是 $1$ 的倍数，即有 $\frac{n}{1}$ 个数的因子包含 $1$

区间 $[1,n]$ 中有 $\frac{n}{2}$ 个数是 $2$ 的倍数，即有 $\frac{n}{2}$ 个数的因子包含 $2$

区间 $[1,n]$ 中有 $\frac{n}{3}$ 个数是 $1$ 的倍数，即有 $\frac{n}{3}$ 个数的因子包含 $3$

.....

int sum = 0;
for(int i = 1; i <= n; i ++){
    sum += (n / i);
}
cout << sum << endl;

实际上就是求 $\sum_{i= 1}^{n}{\frac{n}{i}}$ ，那么就用到数论分块的知识了，否则直接循环超时

总代码：

#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;
}