题意：
给定一个长度为 $n$ 的序列 $a$ ，$n \le 10^6$ ，每个数字 $a_i$ ，满足 $0 \le a_i \le 10^6$ .
可以对这个序列进行一种操作，把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.
问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除（$0$可以被任何数整除），操作过程要满足所有的 $0\le a_i$ 。
题解：
考虑操作完成之后的结果，如果每一个数字都能被 $k$ 整除，那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。
然后显然 $k$ 为合数时的情况，要么被 $k=其质因子$ 的情况包括，要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况，也就是 $S$ 的所有质因子。
由 $S$ 最大为 $10^{12}$ 可知，其质因子最多应该只有$10-20$种，而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法，也就是约 $10^6$ 。
继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”