题解：P10539 [APIO2024] 魔术表演

APIO2024，忆昔当年泪不干。

这个题的解决思路有两种，一种是保存完整的信息不要让信息被删干净，另一种是保存一些有效信息通过删除后剩余的有效信息还原原数。

第一个思路的一种可行做法为 $k$ 进制拆分，先对 $X$ 拆位，每一位连向代表 $0 \sim k - 1$ 的点，多连几遍。随机删点的情况下正确率非常高。

但交互库可能会采取某种特殊策略删点，比如删除某个点连出去的所有边之类的。这样就有很大的可能会丢失信息。

多做几次随机置换能降低丢失信息的概率，最后能不能过比较吃运气。

由这个做法可以延伸到第二个思路的类似做法：我们对 $X$ 做多次 $k$ 进制拆分，每次取不同的 $k$。最后就算删除了相当一部分信息，我们仍然能从剩余的信息里还原出原来的 $X$。

这个做法可行但很麻烦，考虑一个更简单的做法。

把 $k + 1$ 连向 $X \bmod k + 1$，最后 exCRT 还原一下即可（实际上直接暴力还原复杂度也是对的）。

设保留下来的边里的更大的数为 $x_i$，那么最后一定能还原出一个小于所有 $x - 1$ 的最小公倍数的解。

我们只要保证这个最小公倍数大于 $10^{18}$ 即可，为了保证正确性，要把 $n$ 取大一点。