[ABC423G] Small Multiple 2 题解

· · 题解

好题。本题解做法与官方题解相同，但将采用类似 CF Hints 的风格。下文中的 \oplus 均指将两个十进制数进行拼接，|x| 表示 x 在十进制下的位数，且默认包含前导零。

::::info[提示 1]

考虑答案的形式。

:::success[答案]

答案一定是 l \oplus S \oplus r 的形式，其中允许 l, r 有前导零。

:::

::::

::::info[提示 2]

考虑 l 与 r 的限制。

:::success[答案]

最基础地，有 l \oplus S \oplus r \equiv 0 \pmod k，即 l \cdot 10^{ |S| + |r| } + S \cdot 10^{ |r| } + r \equiv 0 \pmod k。同时有 |l| + |r| = |k|（均包含前导零），因为一定存在一个 x 满足：

若 |l| + |r| \gt |k| 则 (l, r) 这一组解严格劣于 (0, x) 这一组解。

:::

::::

:::::info[提示 3]

考虑如何通过暴力枚举找到所有解 (l, r)。

::::warning[尝试与观察]

于是发现第一维需要枚举 |r|。

::::

::::success[答案]

对于第二维，可以枚举 l 并解出 r' 或者枚举 r 并解出 l'，以下对两种情况都进行讨论。

:::success[枚举 l]{open}

请注意，|r| 表示的是钦定的 r 的位数，而实际解出的 r' 不一定满足 |r'| = |r|。

将 l \oplus S \oplus r' \equiv 0 \pmod k 整理一下即可得到 r' \equiv - l \cdot 10^{ |S| + p } - S \cdot 10^p \pmod k，可以 O(1) 解出。注意当且仅当 r' 的有效位数（不包含前导零）\le |r| 合法。

:::

:::success[枚举 r]{open}

同样整理 l' \oplus S \oplus r \equiv 0 \pmod k 可以得到 10^{ |S| + |r| } \cdot l \equiv - S \cdot 10^{ |r| } - r \pmod k，解这个线性同余方程即可得到 l'。这里把扩欧的时间复杂度视为常数。同样当且仅当 l' 的有效位数 \le |k| - |r| 时合法。

:::

::::

:::::

::::info[提示 4]

考虑如何优化暴力。

:::success[答案]

:::

::::

::::info[提示 5]

考虑得到所有解 (l, r) 之后，如何比较 l \oplus S \oplus r 的大小。

:::success[答案]

对于所有 |r| 相同的解 (l, r)，显然可以直接比较 (l, r) 的字典序，字典序最小的解对应的答案就是最小的。

对于 |r| 不同的解，暴力比较即可。总共只会比较 |k| 次。

:::

::::

:::success[提示 6]

于是这道题就做完了。时间复杂度 O(|k|(\sqrt k + |k| + n))。

:::

我的代码写得有点丑，并且写的时候也对照了官方题解代码，所以建议直接去学习官方题解代码。我的代码与官方题解代码实现上唯一的区别是我用了扩欧求解线性同余方程，而官方题解代码用了欧拉定理。