P7200 [COCI2019-2020#1] Lutrija

发布时间 2023-09-22 12:41:16作者: 御坂夏铃

发现相邻的奇数只能恰好差 \(2\)(偶质数只有 \(2\))。

而大于 \(3\) 的三个连续奇数至多有两个是质数,因为有一个能被 \(3\) 整除。对于 3 5 7 这三个数,我们可以构造成 3 5 2 7 以归入下面的构造方法。

所以相邻的奇数最多只有两个。

但我们可以放偶质数 \(2\)。显然,放多个 \(2\) 肯定不优。

于是我们就有 A A-2/A+2 2 B-2/B+2 B 这样的构造形式,根据情况可以省略部分。

这样就能过了,本着精益求精的精神我们继续探究。

\(A\) 来讲,要存在合法的情况必须满足 \(A\) 是孪生质数中的一个。

假设 \(A\)\(A-2\) 是质数,我们显然不需要构造一个 \(A-2\) 项因为 \(A\)\(2\) 的差就是 \(A-2\)

所以就可以少判断 \(A-2\) 这一项啦。

时间复杂度即为判断质数的复杂度。值得注意的是,除了 3 5 7 这种特殊情况,其余构造出来的解都是最短的。