题目大意

给定一个区间 $[l, r]$（$1 \le l \le r \le 10^9$），求其中包含的最小互质区间的数量。

• 区间 $[a, b]$ 是互质区间当且仅当 $\gcd(a, b) = 1$。
• 互质区间 $[a, b]$ 是最小互质区间当且仅当它不包含任何不等于自身的互质子区间。

解题思路

通过分析可知，所有最小互质区间只有两类：

1. 长度为 $1$ 的区间：$[1, 1]$。
   因为 $[x, x]$ 互质当且仅当 $x = 1$（$\gcd(x, x) = x = 1$），且它没有真子区间，所以 $[1, 1]$ 是最小互质的。

2. 长度为 $2$ 的区间：$[i, i+1]$，其中 $i \ge 2$。

   • 相邻整数一定互质，所以 $[i, i+1]$ 是互质区间。
   • 它的真子区间只有 $[i, i]$ 和 $[i+1, i+1]$，由于 $i \ge 2$，这两个单点区间都不互质，因此 $[i, i+1]$ 是最小互质的。

其他任何区间要么本身不互质，要么包含上述两类中的某个作为真子区间，因此都不是最小互质区间。

计数方法

给定 $[l, r]$，我们需要统计所有满足 $i \ge 2$ 且 $[i, i+1] \subseteq [l, r]$ 的 $i$ 的个数，再加上可能存在的 $[1, 1]$。

• 条件 $[i, i+1] \subseteq [l, r]$ 等价于 $l \le i$ 且 $i+1 \le r$，即 $i \in [l, r-1]$。
  同时要求 $i \ge 2$，所以 $i$ 的取值范围是 $[\max(l, 2),\ r-1]$。
  若 $\max(l, 2) \le r-1$，则个数为 $(r-1) - \max(l, 2) + 1$；否则为 $0$。

• $[1, 1]$ 被包含当且仅当 $l \le 1 \le r$，即 $l = 1$。

分类讨论

• 若 $l = r = 1$：此时只有 $[1,1]$，答案为 $1$。
• 若 $l = 1$ 且 $r > 1$：
  $[1,1]$ 贡献 $1$；
  $i$ 的范围为 $[2, r-1]$，个数为 $(r-1)-2+1 = r-2$；
  总数为 $(r-2)+1 = r-1$。而 $r-l = r-1$，所以答案为 $r-l$。
• 若 $l \ge 2$：
  $[1,1]$ 不存在；
  $i$ 的范围为 $[l, r-1]$，个数为 $(r-1)-l+1 = r-l$；
  所以答案为 $r-l$。

综上，除了 $l = r = 1$ 时答案为 $1$，其余情况答案均为 $r-l$。

由于 $l = r = 1$ 时 $r-l = 0$，而正确答案是 $1$，因此只需要特判这一种情况。

时间复杂度

每个测试用例 $O(1)$，总复杂度 $O(t)$，可以轻松通过。

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        if (l == 1 && r == 1) cout << "1\n";
        else cout << r - l << "\n";
    }
    return 0;
}

示例验证

以题目样例为例：

与题目输出完全一致。