lmxcslD

dehsirehC · 2023-10-23 22:15:43 · 题解

n 为质数

解法：其中一种答案序列为 n 个 1 或一个 n ，将两者的较大值输出即可。

证明：对于一个恰好包含 m 个 1 的序列，它的乱斗值不超过 f(m)=m(k-1)^2+(n-m-k)^2 。

容易发现上述解法的答案即为 \max(f(0),f(n)) 。考虑随着 m 的增大 f(m) 的变化规律。

根据上式容易得到当某一个 m' 满足 f(m')\ge f(m'-1) 时，对于任意 m\ge m' 都满足 f(m)\ge f(m-1) 。

换句话说，函数 f(m) 是一个单谷函数，而对于它的极值，必定会在其定义域的两个极值处取到，即 f(0) 或 f(n) 。

k=1

现在我们不需要考虑 p_i-k<0 的情况。感觉一下，发现 p_i 越大性价比越高。

设不超过 n 的最大质数为 P ，如果答案序列包含 P ，我们将问题递归到 (n-P,k) ，否则 p_i<P 。

我们首先忽略掉 p_i 为质数这一条件，若一个序列存在两个数 1\le p_i\le p_j<P-1 ，将 p_j\gets p_j+1 ， p_i\gets p_i-1 一定更优。

这样一直调整下去，当 n-P+1<P 时，最终一定会调整到 p=(P-1,n-P+1) 。

容易发现当 n 比较大时， P 远大于 n-\sqrt n ，即 (P-1)^2\ge (P-2)^2+(n-P)^2 。

具体而言 n-P 的最大值取决于质数间隙，在 n 取到 10^9 时最大质数间隙也不过几百。

当 n 比较小的时候可以暴力 DP ，但实践证明答案序列必定包含 P 。

至于 P 怎么找，可以直接暴力枚举，再 O(\frac{\sqrt n}{\ln n}) 判断是否为质数，由于质数间隙很小且跑不满，故可以通过。

顺带一提，如果 O(\sqrt n) 判断是否为质数也可以通过，感觉很难卡......

正解

我们延续 k=1 时的思路，找到不超过 n 的最大质数 P 。

若答案序列包含超过 n-P 个 1 ，则答案序列必定为 n 个 1 ，证明类似 n 为质数时的思路。

接下来考虑答案序列中 1 的数量不超过 n-P 的情况，如果答案序列包含 P 则依旧将问题递归到 (n-P,k) 。

否则的话首先忽略掉 p_i 为质数这一条件，还是按照 k=1 的思路不断调整序列 p 。

注意可以忽略掉 1<p_i<k 时的情况，因为可以将它们调成 1 使乱斗值更大。

设序列 p 中有 m 个 1 ，当 n-m-P+1<P 时，最终 p 除 1 外仅包含 P-1 和 n-m-P+1 。

根据 n 为质数中的思路，容易得到若 p 包含 P-1 时，剩下的数必定为 n-P+1 个 1 或一个 n-P+1 ， m\ge 1 时矛盾。

现在我们说明了该情况下 m 必定为 0 ，接下来考虑 (P-k)^2 与 (P-k-1)^2+(n-P-k+1)^2 的大小关系。

考虑当 n\le (k-1)^2 时， n^2\le n(k-1)^2 ，即答案序列必定由 n 个 1 组成。

当 n>(k-1)^2 时且 n 比较大时，依旧由于质数间隙很小，故 (P-k)^2 必定大于 (P-k-1)^2+(n-P-k+1)^2 。

当 n 比较小的时候可以暴力 DP ，但实践证明答案序列在这种情况下必定包含 P 。