题目链接：区间因数个数之和_牛客题霸_牛客网
题目大意：对于给定的 l,r，求值在 l∼r 之间的所有整数的因数个数之和，形式化的，求
的值。（1<=l<=r<=10^12)
题目思路:如果暴力求解每个数的因数个数时间复杂度是O(n*n^1/2),那么必然超时，我们可以逆向思维，原问题是对于每个数i，它有多少约数，那么反过来，对于每个约数d,它在那个数的约数列表里
举个例子，区间 [1, 10]：
原视角：
-
6 的约数有：1, 2, 3, 6
反视角：
-
约数 3 出现在：3, 6, 9（3 的倍数）
可以看出：
约数 d 在 1~n 中出现的次数，等于 n 以内 d 的倍数个数，也就是：
⌊n/d⌋
比如 n=10, d=3：⌊10/3⌋ = 3，对应 3, 6, 9
那么1~n所有数的约数个数总和：F(n)=
,每个约数 d 贡献了 ⌊n/d⌋ 次。
对于区间[l,r]所有数的约数个数总和我们可以用前缀和来求解：ans=F(r)-F(l-1)
分析时间复杂度：
现在问题变成了：如何快速计算 F(n) = Σ_{d=1}^n ⌊n/d⌋
直接 for d=1 到 n，n 最大 1e12，还是超时。
观察可以发现整除分块（数论分块）
以 n=10 为例，列出 ⌊10/d⌋ 的值：
| ⌊10/d⌋ | 10 | 5 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
发现：很多连续位置的商是相同的！
-
d=4~5：商都是 2
-
d=6~10：商都是 1
核心思想
既然商相同的区间可以批量处理，那就一次性算一整段，而不是一个一个加。
如何确定每段的左右边界？
假设当前从 d 开始：
-
商 q = ⌊n/d⌋
-
这段的右边界 nxt = ⌊n/q⌋（因为当 i 超过 n/q 时，⌊n/i⌋ 会变小）
这一段 [d, nxt] 内所有 ⌊n/i⌋ 都等于 q。
贡献就是：
q×(nxt−d+1)q×(nxt−d+1)
然后 d 跳到 nxt + 1，继续下一段。
复杂度跃迁
| 暴力枚举每个 d | n 次 | 1e12 次 ❌ |
| 整除分块 | 约 2√n 段 | 约 2e6 次 ✅ |
为什么是 2√n？因为商 q 只有两种类型：
-
q > √n 时，d 很小，最多 √n 种
-
q ≤ √n 时，q 本身只有 √n 种取值
所以总段数 ≈ 2√n。
总体思路：
看到题目 ↓ 暴力枚举每个数 → 发现范围 1e12，超时 ↓ 转换视角：枚举约数而不是枚举数 ↓ 推出 F(n) = Σ⌊n/d⌋ 和前缀和做差 ↓ 发现 ⌊n/d⌋ 有很多连续相同值 ↓ 整除分块优化：批量计算相同段 ↓ 复杂度从 O(n) 降到 O(√n) ↓ AC 通过
代码如下：
#include <bits/stdc++.h>
using namespace std;
using in128 = __int128_t;
#define int long long
//计算F(n)=1~n所有数的约数个数总和
int F(int n){
if(n==0){
return 0;
}
int ans = 0;
int d = 1;
while(d<=n){
int q=n/d;//当前商
int nxt = n / q;//相同商的最右位置
ans+=q*(nxt-d+1);//该分块的总贡献
d=nxt+1;//更新d到下一个分块的最左位置
}
return ans;
}
void solve()
{
int l, r;
cin >> l >> r;
cout << F(r) – F(l – 1) << "\\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin >> T;
while (T–)
{
solve();
}
return 0;
}
