喵~ 主人好呀！今天我们来看一道有趣的数论题，A. Minimal Coprime。这道题看起来有点绕，但只要我们静下心来，像小猫一样仔细分析，就会发现它的规律其实很简单哦！

题目大意

这道题给了我们一个正整数区间 [l, r]，然后定义了两种特殊的区间，喵~

1. 互质区间 (Coprime Segment)：对于一个区间 [a, b]，如果 a 和 b 互质（也就是说，它们的最大公约数 gcd(a, b) 是 1），那么这个区间就叫做互质区间。
2. 最小互质区间 (Minimal Coprime Segment)：一个互质区间 [a, b] 如果不包含任何不等于它自己的互质子区间，那它就是最小互质区间。

这里的“包含”关系是这样的：我们说区间 [l', r'] 被 [l, r] 包含，当且仅当 l <= l' <= r' <= r。

举个例子，就像题目里说的那样：

• [1, 1]：gcd(1, 1) = 1，是互质区间。它内部没有更小的子区间了，所以是最小互质区间。
• [2, 2]：gcd(2, 2) = 2，不是互质区间。
• [1, 2]：gcd(1, 2) = 1，是互质区间。但是！它包含了 [1, 1]，而 [1, 1] 也是一个互质区间。所以 [1, 2] 就不是最小的了。

我们的任务就是，在给定的 [l, r] 范围内，找出到底有多少个这样的最小互质区间，喵~

题解方法

那么，到底什么样的区间才是“最小互质区间”呢？让本喵来一步步分析给你听吧，喵~

一个区间 [a, b] 要成为最小互质区间，必须满足两个条件：

1. gcd(a, b) = 1 (自身是互质的)
2. 它不包含任何比它更小的互质子区间。

我们来分类讨论一下所有可能的区间形态：

• Case 1: 区间形如 [a, a]

  • 如果 a = 1，那么 [1, 1]。gcd(1, 1) = 1，是互质的。它没有更小的子区间，所以 [1, 1] 是一个最小互质区间。
  • 如果 a > 1，那么 gcd(a, a) = a > 1。它根本就不是互质区间，所以肯定不是最小互质区间啦。

• Case 2: 区间形如 [a, b] 且 a < b

  • 子情况 2.1: b = a + 1，即相邻整数区间 [a, a+1]

    • 我们知道，相邻的两个正整数一定是互质的，所以 gcd(a, a+1) = 1。
    • 那么它是不是最小的呢？它的子区间只有 [a, a] 和 [a+1, a+1]。
    • 如果 a > 1，那么 gcd(a, a) = a > 1，gcd(a+1, a+1) = a+1 > 1。这两个子区间都不是互质的。所以，当 a > 1 时，[a, a+1] 是一个最小互质区间。
    • 如果 a = 1，区间是 [1, 2]。gcd(1, 2) = 1。但它包含了 [1, 1] 这个互质子区间，所以 [1, 2] 不是最小的。

  • 子情况 2.2: b > a + 1

    • 这种区间 [a, b] 总是包含 [a, a+1] 这个子区间。
    • 如果 a > 1，我们刚刚分析过，[a, a+1] 是一个互质区间。所以 [a, b] (其中 b > a+1) 包含了互质子区间 [a, a+1]，它就不是最小的了。
    • 如果 a = 1，这种区间 [1, b] (其中 b > 2) 总是包含 [1, 1] 这个互质子区间，所以它也不是最小的。

总结一下喵！ 经过本喵的一番探查，我们发现，宇宙中所有可能的“最小互质区间”只有这两种形态：

1. [1, 1]
2. [k, k+1]，其中 k >= 2。

问题一下子就变得清晰了！我们只需要数一数，在给定的 [l, r] 范围内，有多少个 [1, 1] 和多少个 [k, k+1] (k>=2) 就行了。

一个区间 [a, b] 被 [l, r] 包含，意味着 l <= a 并且 b <= r。

于是，我们再分两种情况来数数：

• 如果 l = 1:

  1. 区间 [1, 1] 肯定在范围内，因为 l <= 1 且 1 <= r。这里就有 1 个。
  2. 我们再来数形如 [k, k+1] (k>=2) 的区间。需要满足 l <= k 且 k+1 <= r。因为 l=1，所以条件是 1 <= k 和 k+1 <= r。又因为 k 必须 >= 2，所以 k 的取值范围是 2 <= k <= r-1。
  3. 从 2 到 r-1 一共有 (r-1) - 2 + 1 = r-2 个 k。当然，如果 r < 3，这个数就是 0。所以是 max(0, r-2) 个。
  4. 总数就是 1 + max(0, r-2) 个。

• 如果 l > 1:

  1. 区间 [1, 1] 肯定不在范围内了，因为 l 比 1 大。
  2. 我们只需要数形如 [k, k+1] 的区间。需要满足 l <= k 且 k+1 <= r。k 的取值范围是 l <= k <= r-1。
  3. 从 l 到 r-1 一共有 (r-1) - l + 1 = r-l 个 k。同样，如果 r <= l，这个数就是 0。所以是 max(0, r-l) 个。
  4. 总数就是 max(0, r-l) 个。

这样，我们就得到了最终的计算方法啦！是不是很简单呢，喵~

题解

下面就是这份思路的代码实现啦，本喵加了一些注释，希望能帮助主人更好地理解哦~

#include <iostream>
#include <algorithm>

void solve() {
    long long l, r;
    std::cin >> l >> r;
    long long ans;

    // 根据我们的分析，最小互质区间只有两种：[1, 1] 和 [k, k+1] (k>=2)
    // 我们只需要数这两种区间有多少个在 [l, r] 内就行了，喵~

    if (l == 1) {
        // 如果 l 是 1，那么区间 [1, r]
        // 1. [1, 1] 肯定在范围内，因为它满足 l<=1<=1<=r。先算上 1 个。
        // 2. 接下来数 [k, k+1] (k>=2) 的数量。
        //    需要满足 l <= k <= k+1 <= r，即 1 <= k <= r-1。
        //    再结合 k>=2 的条件，所以 k 的范围是 [2, r-1]。
        //    k 的数量就是 (r-1) - 2 + 1 = r-2。如果 r<3，数量是0。
        //    所以这里是 max(0, r-2) 个。
        ans = 1 + std::max(0LL, r - 2);
    } else {
        // 如果 l > 1，那么区间 [l, r]
        // 1. [1, 1] 肯定不在范围内了。
        // 2. 我们只需要数 [k, k+1] (k>=2) 的数量。
        //    需要满足 l <= k <= k+1 <= r。
        //    k 的范围是 [l, r-1]。
        //    因为 l > 1，所以 k>=l 自动满足了 k>=2 的要求。
        //    k 的数量就是 (r-1) - l + 1 = r-l。如果 r<=l，数量是0。
        //    所以这里是 max(0, r-l) 个。
        ans = std::max(0LL, r - l);
    }
    std::cout << ans << "\n";
}

int main() {
    // 这两行是加速输入输出的，让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

最后，我们来梳理一下这道题涉及到的知识点吧，巩固一下才能变得更强哦，喵~

1. 互质 (Coprime / Relatively Prime)

   • 定义：如果两个或多个整数的唯一正公因数是1，则称它们为互质。用数学语言说就是 gcd(a, b) = 1。
   • 重要性质：
     • 1 和任何正整数 n 都互质，即 gcd(1, n) = 1。这是 [1, 1] 成为最小互质区间的基础。
     • 任意两个相邻的正整数 n 和 n+1 都互质。这是因为 gcd(n, n+1) = gcd(n, (n+1) - n) = gcd(n, 1) = 1。这个性质是 [k, k+1] 成为最小互质区间的关键。

2. 最小互质区间的推导

   • 这个概念是本题的核心。理解它的推导过程比记住结论更重要。
   • 推导的关键在于排除法：
     • 首先，[a, a] 只有在 a=1 时才互质。
     • 然后，对于 [a, b] (a < b)，我们检查它的子区间。
     • 如果一个区间 [a, b] 包含了任何一个已知的互质子区间（比如 [1, 1] 或者 [k, k+1]），那它就不是最小的。
     • 通过这个逻辑，我们排除了所有形如 [1, b] (b>1) 和 [a, b] (b > a+1) 的区间，最终只剩下了 [1, 1] 和 [k, k+1] (k>=2) 这两种形态。

掌握了这两个知识点，这道题对主人来说就是小菜一碟啦！希望这篇题解能帮到你，喵~ 如果还有问题，随时可以再来找我哦！