J - Jetton - 题解

标签与难度

标签: Game Theory, Simulation, Number Theory, Math, Invariant 难度: 1600

题目大意喵~

有两个玩家 Yuki 和 Ena，她们初始分别有 $x$ 和 $y$ 个筹码。她们玩一个回合制的游戏，规则是这样的呐：

如果两人的筹码数量不相等，那么筹码较少的玩家获胜。
如果两人的筹码数量相等，那么 Yuki 获胜。
输家需要支付给赢家一笔筹码，数量等于赢家当前拥有的筹码数。
当任意一方的筹码数变为 0 时，游戏立刻结束。

我们需要判断游戏是否会在有限的回合内结束。如果会，就输出游戏的总回合数；如果游戏会无限进行下去，就输出 -1，喵~

举个栗子：

(30, 90): Yuki 有 30，Ena 有 90。Yuki 比较少，Yuki 赢！Ena 需要支付给 Yuki 30 个筹码。Yuki 变成 $30+30=60$ ，Ena 变成 $90-30=60$ 。
(60, 60): 现在她们筹码一样多！规则说 Yuki 赢。Ena 支付给 Yuki 60 个筹码。Yuki 变成 $60+60=120$ ，Ena 变成 $60-60=0$ 。
Ena 的筹码是 0 了，游戏结束！总共进行了 2 个回合，喵~

解题思路分析

这道题看起来像是一个复杂的游戏，但只要我们抓住其中的小尾巴，就能发现它的秘密哦，喵~

发现不变量！

让我们来观察一下每回合筹码数量的变化。假设当前两人的筹码是 $(a, b)$ 。

如果 $a < b$ ， $a$ 的持有者赢。新状态是 $(a+a, b-a) = (2a, b-a)$ 。
如果 $b < a$ ， $b$ 的持有者赢。新状态是 $(a-b, b+b) = (a-b, 2b)$ 。

我们来计算一下每回合后的总筹码数：

对于第一种情况，总和是 $2a + (b-a) = a+b$ 。
对于第二种情况，总和是 $(a-b) + 2b = a+b$ 。

看到了吗？无论谁赢谁输，两人的筹码总数 $S = x+y$ 是一个不变量！它从游戏开始到结束都不会改变，就像我对小鱼干的爱一样永恒不变，喵~

游戏如何结束？

游戏结束的条件是某一方筹码变为 0。我们来分析一下最后一步是什么样的。假设游戏在 Yuki 获胜时结束，那么她的筹码会增加，而 Ena 的筹码会归零。这只有在一种情况下会发生：在最后一回合开始前，两人的筹码数量相等，比如都是 $k$ 。根据规则，筹码相等时 Yuki 获胜。Ena 支付给 Yuki $k$ 个筹码，状态变为 $(k+k, k-k) = (2k, 0)$ 。游戏结束！

这意味着，游戏若要结束，必须先到达一个双方筹码相等的状态 $(k, k)$ 。既然总筹码数 $S$ 是不变的，那么在这个状态下，我们有 $k+k=S$ ，也就是 $S=2k$ 。这告诉我们一个至关重要的信息：总筹码数 $S$ 必须是偶数！

如果初始筹码总和 $x+y$ 是奇数，那么无论如何也不可能出现两人筹码相等的情况（因为 $S=2k$ 要求 $S$ 是偶数）。所以，游戏永远不会结束。这是我们的第一个突破口：如果 $x+y$ 是奇数，直接输出 -1！

模拟游戏进程

如果 $x+y$ 是偶数，游戏就一定会结束吗？不一定哦！比如题目样例中的 (15, 55)，总和是 70（偶数），但它就陷入了无限循环。

所以，最可靠的方法就是模拟整个游戏过程！为了方便，我们不妨设当前筹码数较少的一方为 a，较多的一方为 b。每一回合，持有 a 的玩家获胜，状态从 $(a, b)$ 变为 $(2a, b-a)$ 。为了准备下一轮，我们再比较 $2a$ 和 $b-a$ 的大小，把较小的作为新的 a，较大的作为新的 b。然后重复这个过程。

这个过程会一直持续，直到我们遇到 a == b 的情况。假设这花费了 count 个回合。此时，游戏还没有结束哦！还需要最后一回合，从 $(a, a)$ 变为 $(2a, 0)$ 。所以总回合数是 count + 1。

如何处理无限循环？

就像猫咪追自己的尾巴，这个模拟过程可能会陷入一个永远无法到达 a == b 的循环。我们该怎么办呢？可以设置一个“耐心值”，也就是最大模拟次数。比如说，我们模拟 100 回合。如果在 100 回合内还没有分出胜负（即 a 还不等于 b），我们就认为它陷入了无限循环，输出 -1。对于这类题目，如果游戏能结束，通常会在很少的回合内结束（比如几十回合）。所以设置一个像 100 这样的上限是相当安全的策略，喵~

总结一下我们的策略：

计算总筹码 $S = x+y$ 。如果 $S$ 是奇数，游戏永不结束，输出 -1。
否则，开始模拟。用变量 a 存较少的筹码，b 存较多的。
进入一个循环，只要 a != b 就一直进行： a. 记录回合数。如果超过了设定的上限（比如 100），就判断为无限循环，输出 -1 并结束。 b. 根据规则更新筹码：旧的 $(a, b)$ 变为新的 $(2a, b-a)$ 。 c. 重新确定新的 a 和 b（较小者和较大者）。
如果循环正常结束（因为 a == b），说明游戏可以结束。总回合数就是已经过的回合数再加 1。

这样，我们就能完美地解决这个问题啦！是不是很简单呢，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份代码哦！注释很详细，希望能帮到你，呐。

cpp

#include <iostream>
#include <algorithm> // 用于 std::swap 和 std::min/max
#include <numeric>   // 只是为了展示，其实这个题用不到 gcd

// 为了防止筹码数量太大溢出，我们使用 long long，喵~
using int64 = long long;

void solve() {
    int64 x, y;
    std::cin >> x >> y;

    // 关键洞察 1: 检查总和的奇偶性
    // 游戏结束前的状态必然是 (k, k)，总和为 2k (偶数)。
    // 因为总和 S = x+y 是不变量，如果 S 是奇数，则永远无法达到 (k, k) 状态。
    if ((x + y) % 2 != 0) {
        std::cout << -1 << "\n";
        return;
    }
    
    // 如果初始就相等，1回合结束 (Yuki赢, Ena支付, Ena变0)
    if (x == y) {
        std::cout << 1 << "\n";
        return;
    }

    // 为了方便模拟，我们用 a 存储较小值，b 存储较大值
    int64 a = std::min(x, y);
    int64 b = std::max(x, y);

    int rounds_to_equal = 0;
    const int MAX_ITERATIONS = 100; // 设置一个足够大的模拟上限来检测无限循环

    // 模拟游戏直到双方筹码相等
    while (a != b) {
        // 如果模拟次数太多，就认为是无限循环
        if (rounds_to_equal > MAX_ITERATIONS) {
            std::cout << -1 << "\n";
            return;
        }

        // 状态从 (a, b) 变为 (2a, b-a)
        // 这是一个小技巧来更新 a 和 b，而不需要额外的临时变量
        b = b - a; // b 变为差值
        a = a * 2; // a 翻倍

        // 重新排序，确保 a 总是较小的那一个
        if (a > b) {
            std::swap(a, b);
        }
        
        rounds_to_equal++;
    }

    // 循环结束时，我们到达了 (k, k) 的状态。
    // 这花费了 rounds_to_equal 个回合。
    // 还需要最后 1 个回合从 (k, k) 到 (2k, 0)。
    std::cout << rounds_to_equal + 1 << "\n";
}

int main() {
    // 加上这两行，让输入输出更快，对付多组测试数据非常有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(C)$ 每个测试用例。我们的模拟循环有一个固定的上限 MAX_ITERATIONS（我们设为100），所以每个测试用例最多执行常数次操作。因此，对于一个测试用例，时间复杂度是 $O(1)$ 的。对于 $T$ 个测试用例，总时间复杂度是 $O(T \cdot C)$ 。
空间复杂度: $O(1)$ 每个测试用例。在解决每个测试用例时，我们只使用了几个变量来存储筹码数量和回合数，没有使用任何随输入规模增大的额外空间，所以空间复杂度是常数级别的，喵~

知识点总结

不变量 (Invariant): 寻找在问题操作中保持不变的量（比如本题的总筹码数）是解决算法题，尤其是博弈论和数学题的强大武器。
奇偶性分析 (Parity): 检查数字的奇偶性是一个简单但非常有效的技巧，常常能帮你排除大量不可能的情况，快速剪枝。
模拟 (Simulation): 当问题规则清晰，状态转移明确时，直接模拟过程是最直观的解法。
循环检测 (Cycle Detection): 在模拟可能无限进行的游戏或过程中，要记得设置一个迭代次数上限，或者使用更高级的判圈算法（如Floyd判圈法），以避免程序超时。在本题中，一个简单的上限就足够了。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！祝你解题愉快，喵~

J - Jetton - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

发现不变量！ ​

游戏如何结束？ ​

模拟游戏进程 ​

如何处理无限循环？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​