题解：CF2284C1 Disgusting + GCD (Constructive Version)

Ericnoi · 2026-11-13 11:25:15 · 题解

怎么说呢，好像确实没有 C2 吃注意力。

分析

对于第一个限制，我们发现如果最终数组全是质数，那么将满足第一个限制。操作过程方面，注意到 \gcd(a_i,p_i)=1，所以 \gcd(a_i,p_i-a_i)=1，可以一步完成，只要 p_i \ge a_i。

那我们随便找一堆雷霆大质数输出出来，岂不是就是通解了？

实则不然，第二个限制框定了我们的质数不能太胆取大，p_i \ge a_i 的限制又让 p_i 不能大胆取小。看来通用构造什么的没了，不过我们还有一个通用策略：取 p_i 为 \ge a_i 的第一个质数。那么是不是一定能满足第二个限制呢？

其实，如果一定存在 p_i \in [a_i, 2a_i]，那么这个做法就显然满足第二个限制了。不过如果这个性质不成立那么出题人应该就可以构造数据来卡掉。所以这个结论真的成立吗？

这其实就是大名鼎鼎（存疑）的伯特兰-切比雪夫定理。存在比较好理解的初等证明，感兴趣者可自行查找。

但是在比赛中，我们不知道这个定理难道就完蛋了？

其实这个定理是比较好感性理解的。素数的密度大约是 \frac{1}{\log n}，在 [n,2n] 这一大段区间里一个素数都没有是极为反常的，真的有反例很可能也不在题目给出的这么小的范围里存在。比赛的时候大胆猜测这个结论为真就行。

代码实现方面用线性筛搞一下然后二分就行，很平凡。

参考代码略。