题解：P14582 [LNCPC 2025] 被抠的键盘

· · 题解

首先发现 0 是一定没有被抠掉的。如果没有其他别的数字，那么只有 0 显然是无法得到 m 的正整数倍数，输出 -1。

考虑将 m 除去其所有 2,5 因子得到 m'，那么 m' 与 10 互质。由欧拉定理得，10^{\phi(9m')} \equiv 1 \pmod {9m'}，即 \phi (9m') 个 1 是 m' 的倍数。再考虑把 m' 补为 m 的过程，即乘上很多 2 和 5，只需要在我们的构造后面添上足够多的 0 即可。

现在我们得到了仅用 0,1 就能构造的方案，显然把 1 换为任意非 0 数字均成立。由于 m \le 10^7，所以不能直接计算 \phi (9m')。我们预处理到 10^7，然后由 \phi (9m') \mid 18\phi (m') 得，可以输出 18 \phi(m') 个相同的任意没被抠掉的数字，最后输出 10^9 个 0 即可，仅需两步。