题解：CF2109C3 Hacking Numbers (Hard Version)

P_Bisector · 2025-06-21 07:56:35 · 题解

首先我们给出此题两步得到 81 的方案：

mul 999999999
digit

演绎法证明别的题解都有了。但是如果直接去想这个 999999999，十分困难。这里提供一种非常规做法，仅适用于在 IOI 赛制下或已知 f(x)=3 时写出此题。

考虑到把 C2 的代码交进去会有 WA on #1，则 f(x)<4。接下来先构造一个 f(x)=3 的做法。

易证 digit 是必须使用的，否在加乘除无法完成这么复杂的运算。易证 digit 不在第三步，否则当 n>162 时无法完成。易证第一步不是 digit。假设第一步为 digit，则得到此时有 1\leq x\leq 72，然后通过两次操作变为指定的 n，很假。综上，第二步为 digit。

我们注意到 digit 以后只能有一个答案，否则无法归纳到 n。于是我们注意到最后一步应为 add，而 digit 之后得到的 x 一定不变，这里称之为 x_0。那么 digit 之前所得的数的各位数字之和一定不变。

考虑无论是 add 还是 div 都不太能将一个数变成各位数字一定的数，因此考虑 mul 操作。我们将需要 mul 的数称为 m。

这个数是啥呢，好难猜啊。

那不如打表了。

易证 1<m \leq 10^9，那么在这个范围内进行暴力枚举。首先找一个随机的数组，然后比较数组的前两个数与 m 相乘的结果，若各位数字之和相等，则比较后面两个数，以此类推。如果你的数组足够随机，最后只会得到 m=999999999。然后这个时候去归纳或者演绎证明，即可得到 m=999999999 是正确的。

后记

我的朋友：这个题怎么是蓝啊，应该升黑。

直到我写完这篇题解我才意识到为什么会有人标蓝。