题目相关
题目链接（镜像）：Codeforces Round #601 (Div. 1) B2. Send Boxes to Alice (Hard Version)
题目描述：
英文原文我就不打了这里只放个翻译。。。
给定 $n$ 个盒子，第 $i$ 个盒子里有 $a_i$ 块巧克力。一个盒子里可能没有巧克力，但保证肯定存在有巧克力的盒子。
我们希望通过把第 $i$ 个盒子中的巧克力放到第 $i-1$ 或 $i+1$ 个盒子里的操作，实现存在一个 $k(k>1)$ ，使得每个盒子里巧克力个数都是 $k$ 的倍数（当然 $0$ 也是可以的）。
每移动一块巧克力称为一次操作，求最小的操作数。如果无法实现目标就输出 $-1$ 。
输入输出格式：
输入格式：
第一行一个整数 $n$ ，代表盒子数。
第二行 $n$ 个整数，代表每个盒子里巧克力数 $a_i$ 。保证至少有一个 $a_i>0$ 。
输出格式：
如果无解输出 $-1$ 。否则输出最小操作数。
输入输出样例：
| 测试点 | 输入 | 输出 |
|---|---|---|
| #1 | 3 4 8 5 |
9 |
| #2 | 5 3 10 2 1 5 |
2 |
| #4 | 4 0 5 15 10 |
0 |
| #1 | 1 1 |
-1 |
样例解释：
第一个样例：把所有巧克力移到第 $2$ 个盒子中，能被 $17$ 整除。
第二个样例： $2$ 到 $3$ 一块， $4$ 到 $5$ 一块，能被 $3$ 整除。
第三个样例：都是 $5$ 的倍数。
第四个样例：无解。
说明：
$1≤n≤{10}^6$ ，$1≤a_i≤{10}^6$ 。
博主乱搞
蒟蒻解析：
先说无解情况：因为巧克力可以随便移，所以只要有两个及其以上巧克力就肯定有解。因为巧克力不能为 $0$ 个，所以当巧克力和为 $1$ 时便无解。
有解：根据题目，我们知道 $k$ 一定是所有数求和的因数。考虑到最大和为 ${10}^{12}$ ，但我们只需要考虑他的素数因子即可。素数因子不多，我们取其中最小值即可。
按照这种题的套路，最左边的没有前一个的干扰，我们考虑从左到右处理。有一个尴尬的问题是：最优情况是什么？如果我们对第 $i$ 个盒子进行了操作（假设只对右侧更改），也会对之后的情况造成影响，不好找出最优解。
我们换一种思路屏蔽掉对后面的影响：设 $s_n=\sum\limits_{i=1}^{n}{a_i}$ （也就是前缀和），问题求解转化为使得每个前缀和为某个 $k$ 的倍数。这样处理之后，我们把第 $i$ 中巧克力分到 $i+1$ 或者反过来从 $i+1$ 拿给 $i$ ，也不会对 $s_{i+1}$ 造成任何影响。每个元素的问题独立了：我们就可以贪心处理，将每个元素处理为离某个 $k$ 最近的数，求和修改值即可。
考虑是否存在非法情况：调整的时候把其中某个 $a_i$ 搞成负数了？表达在这里就是 $s_i>s_{i+1}$ ？我们可以这样考虑：对第 $i$ 个元素处理，其修改的值最大为 $\frac{k-1}{2}$ （假设 $k$ 是奇数，若是偶数（其实就是 $2$ 了）则把第 $i$ 个的巧克力分给 $i+1$ 保证后面没有负数）。若情况违法，则说明第 $i+1$ 个元素处理后 $a_{i+1}<0$ ，也即 $a_{i+1}<\frac{k-1}{2}$ ，更确切地说： $a_{i+1}≤\frac{k-1}{2}-1$ 。初始最小是 $0$ ，所以最极端情况就是处理后 $a_i=-\frac{k-1}{2}+1>\frac{k-1}{2}$ ，在后续处理中这个数肯定是要被加回 $0$ 的，所以没有影响（相当于后面先补过来了）。
也许还有一种情况是无限继承下去一直是负数？其实情况不存在。我们已经知道任意出现负数的情况肯定处理后被添为 $0$ 。是否都能成功变成 $0$ ？我们已经确保总和是 $k$ 的倍数且不为 $0$ ，最后更改结果一定合法。
蒟蒻代码：
1 |
|
