自动搬运

查看原文

来自洛谷，原作者为

	Starrykiller 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 23:10:28，当前版本为作者最后更新于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$。