P2498. 数字加减游戏

解题思路

题意理解

首先理解题意，b 的使用次数是无限的，我们需要尽可能地少用 a 来使得 s 转化为 t。

差值计算

容易计算 s 和 t 之间的差值的绝对值 diff = abs(s - t)，这是我们需要使用若干个 a 和 b 凑出来的结果。

数学建模

假设我们使用了 x 个 a 和 y 个 b，那么就存在关系 xa + yb = diff。

注意到此时我们并没有区分加减操作，这意味着我们的 x 和 y 是可以取负数的（取负数表示减法）。

问题转化

所以上述问题就转变为，在已知 a、b 和 diff 的前提下，如何选取 y 值，才能使得 x 的绝对值尽可能小。

再换言之，我们可以从 0 开始，从小到大枚举 x，并查看 diff - xa 和 diff + xa 是否可以整除 b，也就是计算得到合适的整数 y。

代码实现

代码非常简短：

复杂度分析 设 diff = |s - t|。

• 时间复杂度：O(b)。while 循环从 0 开始枚举 x，判断条件 (diff - x·a) % b == 0 等价于 x·a ≡ diff (mod b)。x 对 b 的余数只有 b 种可能，因此只要解存在，最小可行的 x 一定落在 [0, b) 之内（更精确地说不超过 b / gcd(a, b)），循环最多执行 b 轮，每轮只做常数次乘法和取模。
• 空间复杂度：O(1)。全程只用 diff、x 等常数个变量。

边界与注意事项

• 「题目保证 s 一定可以变成 t」是 while True 能正常退出的前提：有解意味着 gcd(a, b) 能整除 diff，最小的 x 必然在 b 轮枚举内出现；如果没有这一保证，循环会死循环，实战中可以给 x 加一个不超过 b 的上界兜底。
• s 与 t 的大小关系无需分类讨论：代码先取 diff = abs(s - t)，加减方向是对称的。
• x = 0 的情形已被第一轮判断覆盖：若 diff 本身能被 b 整除（包括 s == t 即 diff = 0 的情况），答案就是 0，一次 a 都不用。
• 条件里同时检查 diff - x·a 与 diff + x·a，对应「这 x 次 a 整体上既可以往加的方向用，也可以往减的方向用」，因此不需要单独讨论 a 的符号选取。