自动搬运

查看原文

来自洛谷，原作者为

	EricWan 一只菜鸡。

搬运于2025-08-24 22:55:03，当前版本为作者最后更新于2024-02-15 12:31:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们充分发扬人类智慧：

假如一个数不是合法的 $K$ 则它的倍数也不是。

根据数学直觉，虽然 $K\in[1,10^9]$，$K$ 的质因数有极大概率均小于等于 $10^7$。

所以我们线性筛 $10^7$ 中的所有质数，之后对于每一个质数 $p$ 找到最大的 $pow_p$ 使得 $p^{pow_p}\in\{K\}$，那么合法的 $K$ 就最多有 $\prod (pow_p+1)$ 个。

再次根据数学直觉，$\prod (pow_p+1)$ 不会很大，DFS 一遍即可，DFS 过程中记得剪枝。

这样速度快得飞起，在 $n=10000$ 时都可以在 200ms 内过。

Q&A：

Q1：每次判断一个数是否是合法的 $K$ 是 $O(n)$ 复杂度的，怎么办？

A1：首先，我们对天数排重，如果这个数是合法的 $K$，的确是 $O(n)$ 的，但是如果不是，前几个数就可以让余数数量很多，直接跳出即可。

Q2：我这样写了，但是只有 65 分，怎么办？

A1：是的，上面的逻辑很难卡掉，但是还是有漏洞，对于天数的取值只有小于等于三个时，$[1,\frac{\max_{i=1}^na_i}4]$ 中的整数都是合法的 $K$，因此，我们特判这种情况，就可以过了。

求赞