[CF2029E] Common Generator 题解

Exp10re · 2024-11-15 16:18:20 · 题解

我很喜欢这一场的 E 和 F，有一种独特的 CNOI 味道。

也就是，如果你按部就班一步一步进行推导，写出这一类题目不会太难。

解题思路

根据定义，我们可以得到一个基础结论：若 p 能被表示，则所有满足 \operatorname{gcd}(p,q)\ne 1 且 q\gt p 的 q 都能被表示。

观察样例可以得到若干结论，我们尝试对其一一进行证明。

引理 1：

若原数列中存在质数，且其不是唯一最小的一个数，则无解。

若原数列中存在质数，则你必须选择这个质数，否则无解。

证明 1：

考虑到你选取的数一定是你能生成的数中最小的一个，故你不可能选取比 \min\limits_{1\leq i \leq n} a_i 大的数。

根据基础结论，你必须选择某个质数，才能构造该质数，故若存在大于等于两个质数，则无解，否则你必须选择该质数，根据上面的小结论，如果这个质数不是最小值，则无解。

综上所述，引理得证。

问题转化为你选取了一个固定的数，对每个数你需要判断该数能否被生成。

考虑你选取了质数 p 之后，下一个能生成的数必定是 2p，并且不难发现，小于 2p 的数一定不能被生成，大于等于 2p 的偶合数一定可以被生成。

接下来考虑大于 2p 的奇合数能否被生成。

引理 2：

记 l_x 表示 x 的最小质因子，一个奇合数 k 能被生成，当且仅当 k-l_k\geq 2p。

证明 2：

先考虑充分性：若 k-l_k\geq 2p 成立，那么一条成立的生成路径是 p\rightarrow 2p \rightarrow k-l_k \rightarrow k。

再考虑必要性：考虑该引理必要性的等价命题：若 k-l_k\lt 2p，则奇合数 k 不能被生成。

考虑到生成 k 必须先生成一个数 t 满足：t\lt k 且 \operatorname{gcd}(t,k)\ne 1。

尝试证明与之相关的两个小引理：

引理 2.1：

对于任意奇合数 d，均有：任意能通过一次操作生成 d 的偶数 t 都满足 t\leq d-l_d。

证明 2.1：

考虑反证法：假设 t\gt d-l_d 且能通过一次操作生成 d 的偶数 t 存在，则有 \operatorname{gcd}(t,d)=\operatorname{gcd}(d-t,d)\ne 1。