变幻莫测

思路

拿到这道题先别急，想一下：两种操作——交换 (X, Y) -> (Y, X) 和变换 (X, Y) -> (X+Y, X-Y)，要让 X 等于 Y，什么情况下做得到？

关键观察：变换操作 (X, Y) -> (X+Y, X-Y) 之后，新的两个数的乘积是 (X+Y)(X-Y) = X^2 - Y^2。如果 X != Y 且 X != -Y 且 XY != 0，那变换之后两个数都不为零，且绝对值也不相等。交换操作只是翻转顺序，不改变这个性质。

所以不管你怎么折腾，只要初始 X 和 Y 既不相等、也不互为相反数、也没有谁是零，那就永远凑不出 X = Y，直接输出 -1。

分情况讨论

那什么时候能凑出来呢？其实就四种情况：

  1. X == Y：已经相等了，0 步
  2. Y == 0：做一次变换 (X, 0) -> (X, X)，1 步
  3. X == 0：先交换 (0, Y) -> (Y, 0)，再变换 (Y, 0) -> (Y, Y)，2 步
  4. X == -Y（且不为零）：变换 (X, -X) -> (0, 2X)，交换 (2X, 0)，变换 (2X, 2X)，3 步

其他所有情况都是 -1。

为什么其他情况不可能？

核心不变量：如果当前 X != 0 且 Y != 0 且 |X| != |Y|，那做变换后 X+Y != 0 且 X-Y != 0（因为 X != -Y 且 X != Y），而且 |X+Y| != |X-Y|（因为这等价于 XY = 0，矛盾）。交换不改变这些性质。所以这组状态是"封闭"的，永远走不到 X = Y。

代码

#include <iostream>
using namespace std;

int main() {
    long long x, y;
    cin >> x >> y;
    if (x == y) {
        cout << 0 << endl;
    } else if (y == 0) {
        cout << 1 << endl;       // 变换一次搞定
    } else if (x == 0) {
        cout << 2 << endl;       // 交换 + 变换
    } else if (x == -y) {
        cout << 3 << endl;       // 变换 + 交换 + 变换
    } else {
        cout << -1 << endl;      // 不可能
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong();
        if (x == y) {
            System.out.println(0);
        } else if (y == 0) {
            System.out.println(1);       // 变换一次搞定
        } else if (x == 0) {
            System.out.println(2);       // 交换 + 变换
        } else if (x == -y) {
            System.out.println(3);       // 变换 + 交换 + 变换
        } else {
            System.out.println(-1);      // 不可能
        }
    }
}

x, y = map(int, input().split())
if x == y:
    print(0)
elif y == 0:
    print(1)
elif x == 0:
    print(2)
elif x == -y:
    print(3)
else:
    print(-1)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const parts = lines[0].trim().split(' ');
    const x = BigInt(parts[0]);
    const y = BigInt(parts[1]);
    if (x === y) {
        console.log(0);
    } else if (y === 0n) {
        console.log(1);
    } else if (x === 0n) {
        console.log(2);
    } else if (x === -y) {
        console.log(3);
    } else {
        console.log(-1);
    }
});

复杂度分析

  • 时间复杂度: ，纯分类讨论，常数时间
  • 空间复杂度: ，只用了两个变量

总结

这题看着像 BFS 搜索，但仔细想想会发现状态空间是无限的，硬搜肯定不行。真正的突破口是分析"什么时候不可能"——当 X 和 Y 都非零且不互为相反数时，变换操作只会让数越来越大，永远凑不出相等。剩下的情况就那么几种，手推一下操作序列就完事了。典型的"看起来复杂，想清楚后几行代码"的数学题。