A. Adjacent Digit Sums 详细题解

问题理解

给定两个正整数 $x$ 和 $y$，问是否存在一个整数 $n$，使得 $S(n)=x$ 且 $S(n+1)=y$，其中 $S(a)$ 表示十进制数 $a$ 的各位数字之和。

---

核心观察

当 $n$ 加 $1$ 时，其十进制表示的变化规律：

• 如果 $n$ 的末尾不是 $9$，则 $n+1$ 只是最后一位 $+1$，其他位不变
• 如果 $n$ 的末尾有 $k$ 个连续的 $9$（$k \ge 1$），则这 $k$ 个 $9$ 变成 $0$，前一位 $+1$，更前面的位不变

因此，$S(n)$ 与 $S(n+1)$ 的关系：

• 情况一（末尾不是 $9$）：$S(n+1) = S(n) + 1$
• 情况二（末尾有 $k$ 个 $9$）：$S(n+1) = S(n) - 9k + 1$，其中 $k \ge 1$

---

推导条件

设 $x = S(n)$，$y = S(n+1)$。

由情况一：$y = x + 1$ 是可能的（只需 $n$ 末尾不为 $9$）。

由情况二：$y = x - 9k + 1$，其中 $k \ge 1$，即 $x + 1 - y = 9k$。

因此：

• $x + 1 - y$ 必须是 $9$ 的正整数倍，即 $x + 1 - y \ge 9$ 且能被 $9$ 整除
• 同时由 $k \ge 1$ 得 $x + 1 - y \ge 9$

注意：当 $y = x + 1$ 时，$x + 1 - y = 0$，不是 $9$ 的正整数倍，所以不属于情况二，但属于情况一。

---

最终判断条件

存在满足条件的 $n$ 当且仅当：

1. $y = x + 1$，或
2. $y \le x$ 且 $(x + 1 - y) \bmod 9 = 0$

为什么 $y \le x$？因为从 $y = x - 9k + 1$ 得 $y = x + 1 - 9k \le x$（因为 $k \ge 1$）。所以情况二必然满足 $y \le x$。

反之，如果 $y > x$ 且 $y \ne x + 1$，则不可能（因为 $y = x + 1$ 是唯一的增加情况，其他情况都会减少或不变？实际上 $y$ 也可能等于 $x$ 吗？$y = x$ 需要 $x + 1 - x = 1$ 不是 $9$ 的倍数，所以不可能。所以 $y > x$ 时只能是 $y = x + 1$）。

---

等价写法

条件可以合并为：

$$y = x + 1 \quad \text{或} \quad (x + 1 - y) \bmod 9 = 0 \ \text{且} \ y \le x $$

注意：当 $y = x + 1$ 时，$(x + 1 - y) \bmod 9 = 0$ 也成立（因为 $0 \bmod 9 = 0$），所以其实可以简化为：

存在 $n$ 当且仅当 $(x + 1 - y) \bmod 9 = 0$ 且 $y \le x + 1$，同时排除 $y = x$ 的情况？

验证：$y = x$ 时，$x + 1 - x = 1$，$1 \bmod 9 \ne 0$，所以自动排除。
$y = x + 1$ 时，$0 \bmod 9 = 0$，且 $y \le x + 1$ 成立。
$y > x + 1$ 时，$x + 1 - y < 0$，模 $9$ 可能为 $0$（例如 $x=1, y=11$，$x+1-y = -9$，模 $9$ 为 $0$），但 $y > x + 1$，这种情况实际上不可能（因为 $n$ 和 $n+1$ 的数字和最多相差 $9k-1$ 且 $k \ge 1$ 时 $y < x$，不能 $y > x+1$）。所以需要额外限制 $y \le x + 1$。

更严格的条件：

$$(x + 1 - y) \bmod 9 = 0 \ \text{且} \ y \le x + 1 \ \text{且} \ y \ne x $$

但 $y = x$ 已被模条件排除，所以只需要：

$$(x + 1 - y) \bmod 9 = 0 \ \text{且} \ y \le x + 1$$

然而 $y = x + 10$ 时，$x+1-(x+10) = -9$，模 $9$ 为 $0$，但 $y = x+10 > x+1$，实际不可能。所以必须 $y \le x + 1$。

因此最终简洁判断：

$$\boxed{(x + 1 - y) \bmod 9 = 0 \ \text{且} \ y \le x + 1} $$

---

示例验证

$x$	$y$	$x+1-y$	模 $9$	$y \le x+1$	结论
1	2	0	0 ✅	2 ≤ 2 ✅	Yes
77		1	1 ❌	—	No
997	999	-1	8 ❌
999	1	999	0 ✅	1 ≤ 1000 ✅	Yes
1000		1000	1 ❌	—	No
1	11	-9	0 ✅	11 ≤ 2 ❌
18	1	18		1 ≤ 19 ✅	Yes

与题目输出完全一致 ✅

---

构造方法（证明存在性）

• 若 $y = x + 1$：取 $n = 10^{x-1}$（$1$ 后面跟 $x-1$ 个 $0$），则 $S(n)=1$？不对，应该是 $n = 10^{x-1}$ 时 $S(n)=1$，不是 $x$。正确构造：取 $n$ 为 $x$ 个 $1$ 组成的数？那样 $S(n)=x$，但 $S(n+1)$ 会进位，不是 $x+1$。实际上更简单的构造：$n = 10^{x-1} + 10^{x-2} + \dots + 10^0 = 111\ldots1$（$x$ 个 $1$），则 $S(n)=x$，$S(n+1)=x+1$ 当最后一个数字不是 $9$ 时成立，这里末尾是 $1$，所以成立。例如 $x=1$，$n=1$，$S(1)=1$，$S(2)=2$。$x=2$，$n=11$，$S(11)=2$，$S(12)=3$。对的。

• 若 $x+1-y=9k$（$k \ge 1$）：取 $n$ 为末尾有 $k$ 个 $9$，前面数字和为 $x - 9k$ 的数。例如，取 $n$ 由 $x-9k$ 个 $1$ 后跟 $k$ 个 $9$ 组成，则 $S(n)=x-9k+9k=x$，$n+1$ 会进位使 $k$ 个 $9$ 变 $0$，前一位 $+1$，因此 $S(n+1)=x-9k+1 = y$。

---

复杂度

每个测试用例 $O(1)$ 时间，总复杂度 $O(t)$。

---

总结

本题的关键是理解 $n$ 与 $n+1$ 数字和的变化规律，将其分为“末尾非 $9$”和“末尾有连续 $9$”两种情况，分别得到 $y = x+1$ 和 $y = x - 9k + 1$（$k \ge 1$）。最终判断条件可统一为 $(x+1-y) \bmod 9 = 0$ 且 $y \le x+1$。