【题解】P11818 [PA 2019 Final] 一安在？ / Gdzie jest jedynka? 2

Starrykiller · 2025-02-24 20:47:59 · 题解

组题人的口胡题解。

问 \gcd(p_0,p_1),\gcd(p_0,p_2),\ldots,\gcd(p_0,p_{n-1})，记答案数列为 a_1\sim a_{n-1}。

如果 a 数列全部是 1，显然 p_0=1。

如果 a 数列是 1\sim n-1 的排列，显然 p_0=0。

以上两种情况平凡。否则，2\le p_0\lt n。

考虑核心的性质：\gcd(a,0)=a。注意到，\gcd(p_0,p_i)\le p_0 当且仅当 p_0\mid p_i 时取到等号。那么，我们将 a_i 取到最大值的位置拿出来递归地做这样的过程。

最终一定会得到 0 的位置。到此询问次数最坏是 n+n/2+n/4+...=2n 的，当每一步都取到 2,4,8,... 时得到最劣解。

最后用 0 再问一遍序列（只需要问不是 p_0 倍数的位置）得到答案。这样最坏卡到 2.5n。