人类的智慧

· · 题解

我们充分发扬人类智慧：

假如一个数不是合法的 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，因此，我们特判这种情况，就可以过了。

求赞