Moe's CF Life

喵~ 主人，今天我们来看一道有趣的题目，是关于寻找一个数学小悖论的反例哦！你的朋友提出了一个猜想，但好像有点小问题，我们来帮他找到问题所在吧，嘻嘻~

题目大意

这道题是说呀，你的朋友学了“互质数”之后，提出了一个猜想：如果 (a, b) 是互质的，并且 (b, c) 也是互质的，那么 (a, c) 也一定是互质的。

我们的任务呢，就是当一个“小坏蛋”，找出这个猜想的一个反例 (Counterexample)。具体来说，我们需要在一个给定的区间 [l, r] 内，找到三个不同的整数 a, b, c，满足以下所有条件：

l ≤ a < b < c ≤ r (三个数都在给定的区间内，并且严格递增)
gcd(a, b) = 1 (a 和 b 互质)
gcd(b, c) = 1 (b 和 c 互质)
gcd(a, c) ≠ 1 (a 和 c 不互质)

如果能找到这样的一组 (a, b, c)，就把它输出。如果找不到，就输出 -1。

注意哦，l 和 r 的值可能会非常大 (达到 10^18)，但是它们的差 r - l 不会超过 50。这是一个非常重要的提示喵！

解题思路

一看到这种要找特例的题目，我们就要动动我们的小脑袋瓜，想办法“构造”一个满足条件的东西出来，而不是傻乎乎地去遍历，那样肯定会超时的说。

我们要让 a 和 c 不互质，最简单的方法是什么呢？当然是让它们有共同的因子呀！最常见的公因子就是 2 啦，也就是说，我们可以尝试让 a 和 c 都是偶数。

那么 b 怎么办呢？b 必须和 a 互质，也要和 c 互质。如果 a 和 c 都是偶数，那 b 最好就是个奇数啦。

这么一来，一个绝妙的组合就浮现在我们眼前了：偶数, 奇数, 偶数。

最简单的满足这个模式的组合是什么呢？当然是三个连续的整数啦！比如 (x, x+1, x+2)。

让我们来验证一下这个组合：

让 a = x 是一个偶数。
那么 b = x + 1 就是一个奇数。
c = x + 2 就是下一个偶数。

现在我们来检查互质关系：

gcd(a, b) = gcd(x, x+1)：相邻的两个整数永远是互质的，所以它们的 gcd 永远是 1。满足条件，喵~
gcd(b, c) = gcd(x+1, x+2)：同样是相邻的两个整数，gcd 也永远是 1。也满足条件，太棒啦！
gcd(a, c) = gcd(x, x+2)：因为 x 和 x+2 都是偶数，它们至少有公因子 2，所以它们的 gcd 肯定大于 1。这不就不互质了嘛！完美地达成了我们的“破坏”目标！

所以，我们的问题就简化成了：在 [l, r] 区间内，能不能找到一个偶数 a，使得 a, a+1, a+2 这三个数都在这个区间里。

也就是说，我们只需要找到一个偶数 a，满足 l ≤ a 并且 a + 2 ≤ r。

怎么找呢？

我们可以从 l 开始。
如果 l 本身就是个偶数，那我们就让 a = l。我们只需要检查 l + 2 是不是小于等于 r。如果是，那么 (l, l+1, l+2) 就是我们要的答案！
如果 l 是个奇数，那大于等于 l 的第一个偶数就是 l+1。我们就让 a = l+1。然后检查 (l+1) + 2 是不是小于等于 r。如果是，那么 (l+1, l+2, l+3) 就是答案啦。

如果上面两种情况都找不到满足条件的 a，说明这个区间太小了，塞不下我们构造的这三个数。因为 r - l 最大只有 50，如果连这么简单的构造都找不到，那更复杂的构造也基本不可能存在了。所以，如果找不到，就说明没有答案，输出 -1 就好啦。

题解代码

这是咱家写的 C++ 代码，思路和上面说的一模一样哦，还加了可爱的注释，喵~

cpp

#include <iostream>

// gcd 函数不是必需的，因为我们通过构造法保证了互质关系
// 但为了知识点的完整性，可以了解一下
// long long gcd(long long a, long long b) {
//     return b == 0 ? a : gcd(b, a % b);
// }

int main() {
    // 使用这个可以让输入输出更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long l, r;
    std::cin >> l >> r;

    // 我们的目标是找到 a, b, c 满足：
    // 1. l <= a < b < c <= r
    // 2. gcd(a, b) = 1
    // 3. gcd(b, c) = 1
    // 4. gcd(a, c) != 1
    
    // 我们构造的万能反例是 (偶数, 奇数, 偶数)
    // 最简单的就是连续的三个数 (x, x+1, x+2)，其中 x 是偶数。
    
    // 首先，我们要找到区间内第一个偶数。
    // 如果 l 本身是奇数，那我们就从 l+1 开始看。
    if (l % 2 != 0) {
        l++; // l 现在是大于等于原 l 的第一个偶数了
    }

    // 现在 l 是我们要找的偶数 a 的候选值。
    // 我们需要检查 a, a+1, a+2 是否都在 [l, r] 区间内。
    // 因为我们已经保证了 l >= 原始的l，所以 a 肯定在区间内。
    // 我们只需要检查 c，也就是 l+2 是否在区间内。
    if (l + 2 <= r) {
        // 如果 l+2 也在区间内，说明我们找到了！
        // a = l, b = l+1, c = l+2
        std::cout << l << " " << l + 1 << " " << l + 2 << std::endl;
    } else {
        // 如果连 l+2 都超出范围了，说明这个区间太窄了，
        // 容不下我们这组可爱的反例。
        // 那就说明不存在这样的反例啦。
        std::cout << -1 << std::endl;
    }

    return 0;
}

题目大意

解题思路

题解代码

相关知识点介绍

1. 互质数 (Coprime Numbers)

2. 最大公约数 (Greatest Common Divisor, GCD)

3. 构造法 (Constructive Approach)

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点介绍 ​

1. 互质数 (Coprime Numbers) ​

2. 最大公约数 (Greatest Common Divisor, GCD) ​

3. 构造法 (Constructive Approach) ​

题目大意

解题思路

题解代码

相关知识点介绍

1. 互质数 (Coprime Numbers)

2. 最大公约数 (Greatest Common Divisor, GCD)

3. 构造法 (Constructive Approach)