2024/03/13(#23)：星解

加训。

[CF1091G] New Year and the Factorisation Collaboration

Portal.

询问 sqrt(x * x)，我们有 $(x-y)(x+y)\equiv 0\pmod n$。排除其中有 $0$ 和 $n$ 的情况，这样我们将 $n$ 的质因子分成两组 $S_1$。

一个质因数 $p_i$ 能被求出，仅当所有 $p_j(j\ne i)$，存在一个 $S$ 使得 $p_j$ 在 $S$ 中出现但 $p_i$ 未出现（注意 $S=1$ 是废票）。

分解成 $k$ 个 $x^2-x'^2\equiv 0\pmod {p_i}$，可以得知模 $n$ 意义下的二次剩余有 $2^k$ 个，但是交互库并不知道我们的 $x$ 是哪个，因此有 $1-2^{-k}$ 的概率返回一个不同的。

同时，$p_i$ 在 $x-x'$ 里时，$p_j$ 也在 $x-x'$ 的概率是 $50\%$，因此 $S$ 是随机分配的。

随机做 $t$ 次，一个 $(i,j)$ 的正确率为 $1-2^{-t}$。最终正确率是 $(1-2^{-t})^{k^2}$。

[CF1286C2] Madhouse (Hard version)

Portal.

没补过 Hard ver.，我是摆怪。

Easy Ver. 做过，这个也差不多，就问 $[1,\frac n 2],[1,\frac n 2 + 1]$，然后剩下的依次考虑长度为 $2\sim \frac n 2$ 的子串，$2$ 的时候排除掉在 $[1,\frac n 2 + 1]$ 里的，然后删掉 $\frac n 2 + 1$ 这个位置的数，就只有 $s_n$ 出现了奇数次，以此类推。

于是恰好预处理到这个位置，后半部分就可做了。代码。