最近的一些 CF 题（9.1起）

1. CF623B

B. Array GCD

先考虑没有操作 2 的情况，由于不允许全删，所以至少会留下 \(a_1\) 与 \(a_n\) 中的一个，那么它们的质因数中必有一个需要成为公因数，由于 最大公因数 是 公因数 的倍数，所以这样是满足 \(\gcd > 1\) 的充要条件。

现在加入了操作 2，那么就把 \(a_1, a_n, a_1\pm 1, a_n \pm 1\) 这 \(6\) 个数全部分解质因数。

对于每个质因数 \(p\)，我们都使其成为公因数并 dp 一次。

假设当前处理到第 \(i\) 位：

• \(dp_{i, 0}\) 表示未删的最小花费；
• \(dp_{i, 1}\) 表示正在删（第 \(i\) 位也删）的最小花费；
• \(dp_{i, 2}\) 表示已删（第 \(i\) 位不删）的最小花费。

转移方程非常好推，就不放在题解中了。

单个质因数 \(p\) 的答案为 \(\min\{dp_{n, 0}, dp_{n, 1}, dp_{n, 2}\}\)。

解释一下为什么这样不会取到全删的情况，因为这样还不如保留 \(a_1\) 或 \(a_n\)。

Code