CF2029E Common Generator
题目描述
称一次操作为，对一个数 x_0 加上其任意大于 1 的因数得到 x_1。
若某数 x 做任意次操作可以得到数 y，则称 x 生成了 y。
现给定 n 个不同的数 a_i，求是否存在一个 x\gt 1 使得 x 可以生成所有的 a_i。无解输出 -1。
### 解法
显然一个质数只能被其自身生成，而任意合数均可被 $2$ 生成。
那么分类讨论，如果存在两个以上的质数，一定无解；
如果存在一个质数，则需判断其能否生成所有数；
如果不存在质数，$2$ 一定是一个合法解。
下面阐释如何判断某质数 $p$ 能否生成数 $x$。
该质数的第一步只能是 $p\to 2p$，则要求 $x\ge 2p$。此时 $2p$ 已然可以生成所有比它大的偶数。那么若 $x$ 为一个偶数，结束。
否则，考虑最大的可以生成 $x$ 的数。显然其为 $x-p_x$，其中 $p_x$ 为 $x$ 最大的质因数。容易发现这个数一定为一个偶数。因此此时只需 $2p\le x-p_x$ 即可。
由以上讨论，正确性是容易证明的。
时间复杂度 $O(n+V)$。