题目链接 - https://codeforces.com/contest/1780/problem/E
给定一张无向图，其中有 \(R - L + 1\) 个点，编号从 \(L\) 到 \(R\)，每两个点 \(u\)，\(v\) 间连一条边，边权为 \(gcd(u,v)\)，问该图有多少种边权
考虑每种边权是否存在于这张图上，对于 \(i\)，若其不存在于这张图的边权上，则该区间一定不存在任意 \(x\)，满足 \(i | x\)，使得 \(x + i\) 也存在于这个区间，反之边权 \(i\) 存在
于是我们需要找到所有满足 \(\lfloor\frac{R}{i}\rfloor > \lceil\frac{L}{i}\rceil\) 的 \(i\)
考虑整除分块，对于连续的一段 \(i\in [l, r]\)，这一段里的 \(i\) 不一定全部满足，容易考虑到我们需要找到最小的 \(x\)，使得 \(\lceil\frac{L}{x}\rceil < \lfloor\frac{R}{i}\rfloor\)，则 \(x = \lceil\frac{L}{\lfloor\frac{R}{i}\rfloor - 1}\rceil\)
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using i64 = long long;
const int N = 2e6 + 10, inf = 0x3f3f3f3f;
void solve() {
i64 L, R, ans = 0; std::cin >> L >> R;
if (R >= 3 * L) {
printf("%lld\n", R / 2); return;
}
for (i64 l = 1, r; l <= R; l = r, l++) {
i64 t = R / l; r = R / t;
if (t == 1) continue;
ans += std::max(0ll, r - std::max(l, (L + t - 2) / (t - 1)) + 1);
}
printf("%d\n", ans);
}
int main() {
int T; std::cin >> T;
while (T--) solve();
return 0;
}