题意：
给定一个长度为 $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$ 。
那么我们就可以分解出来所有可能的 $k$ ，枚举他们来进行下一步的计算。现在问题就转化成了，给定一个数字 $k$ ，问最少需要多少次操作使得这个序列里所有的数字可以被 $k$ 整除。
按照每一个位置上的数字来看似乎很难计算出最优解，但是我们可以把所有的转移一视同仁作为一次操作，然后计算每一个间隔的贡献。
下文 $S_{i}$ 表示 $\sum_{j=1}^{i} a_{j}$
从第一个数字开始考虑，$1$到$2$之间的间隔（不妨把间隔视为传输每一个单位的管道）需要传递 $S_{1}\%k$ 或者 $k-S_{1}\%k$ 个单位才能让 $a_{1}\%k=0$ 。
由于我们要求的结果是最小值，所以这里可以尝试一下：先假定取了$min$，也就是我们先假设这根管道的贡献是 $min(S_{1}\%k,k-S_{1}\%k)$ 。
然后再考虑2到3之间的管道，类似于1到2的情况，要使得前2个数字都被$k$整除，则一定传递了 $S_{2}\%k$ 或者 $k-S_{2}\%k$ 个单位。$
注意：我们处理的顺序保证了，每次只需要考虑当前这个间隔的情况，比如我考虑2到3的间隔的时候就不需要考虑1到2的，我只需要保证我在这个间隔处往前面传递了$S_{2}\%k$ 或者 $k-S_{2}\%k$ 个单位就行了。至于传给$a_{2}$后它怎么处理，不需要担心，它无论收到多少个，只需要保证在1到2的管道中传给了$a_{1}$ $S_{1}\%k$ 或者 $k-S_{1}\%k$ 个单位就可以了。
这样从前往后考虑过每个管道之后，假如到最后一个数字 $a_{n}$ 我们还可以往前传递所需要的数字，也就是说有合法的解，我们就可以计算出所需要的答案了。
因此现在问题变成了，我们在每一步的时候这样贪心的选择，是否能得到合法的解？答案是肯定的。主要原因是我们确定了$k$ 是 $S_{n}$ 的因数，然后在每一步的过程中都凑齐令 $S_{i}$ 为k的倍数，这样就永远可以满足条件。比如拿最后一个数字来说，假如 $a_{n}$不能对 $S_{n-1}$ 凑齐 $k$的倍数，那么 $k \nmid (S_{n-1}+a_{n})$，这与 $k$ 是 $S_{n}$ 的因数是矛盾的，所以一定可以满足条件。以此往前类推，我们就可以证明按照我们的贪心策略，所有的 $S_{i}$ 都是可以合法构造的。至此这道题目就做完了。
wa点：
- $INF$设置小了，原来以为 $10^{12}$ 就足够了，其实还要考虑到转移路径比较长的情况。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll tot,a[maxn],sum[maxn],fac[maxn];
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i],sum[i]=a[i]+sum[i-1];
}
tot=sum[n];
if(tot==1){
cout<<-1;
return 0;
}
if(tot%2==0){
fac[++fac[0]]=2;
while(tot%2==0) tot>>=1LL;
}
for(ll i=3;i*i<=tot;i+=2){
if(tot%i==0){
fac[++fac[0]]=i;
while(tot%i==0) tot/=i;
}
}
if(tot!=1){
fac[++fac[0]]=tot;
}
ll ans=1e18+7,tmp,k;
for(int i=1;i<=fac[0];++i){
tmp=0,k=fac[i];
for(int j=1;j<=n;++j){
tmp+=min(sum[j]%k,k-sum[j]%k);
}
ans=min(tmp,ans);
}
cout<<ans;
return 0;
}