题意：
给定非负数组，每次操作可以选一个 \(a_i\neq 0\)，令 \(a_i\) 减一，\(a_i\) 相邻的一个数（如果存在）加一。问最少几次操作能使所有数有 \(>1\) 的公因数
\(n, a_i\le 1e6\)
思路：
首先公因数取质数肯定更优，所以只需枚举数组总和的质因子。
然后考虑原数组的前缀和数组：原数组的每个数都是某 \(p>1\) 的倍数，等价于前缀和数组的每个数都是 \(p\) 的倍数
每次操作相当于选择一个位置 \(i\)，要求 \(s_{i-1}\neq s_{i}\)，令 \(s_{i-1}\) 加一或令 \(s_i\) 减一
对一个前缀和数组，若所有数非负，且对任何相邻数均有左数不大于右数，则称这个前缀和数组是合法的。容易发现，原前缀和数组可以经过一系列操作变成任一合法的前缀和数组（当然 \(s_n\)）不能变，每一步操作后均合法，且每个 \(s_i\) 的改变是单调的
所以把每个 \(s_i\) 改成最接近的 \(p\) 的倍数即可
const signed N = 5 + 1e6;
ll n, s[N];
ll cal(ll p) { //p也要开ll
ll sum = 0; for(int i = 1; i <= n; i++)
sum += min(s[i]%p, p - s[i]%p);
return sum;
}
void sol() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i-1];
if(s[n] == 1) return cout << -1, void(); //注意特判
ll ans = LLINF;
for(int p = 2; p <= 1e6; p++) if(s[n] % p == 0) { //找s[n]的所有不同质因子
ans = min(ans, cal(p));
while(s[n] % p == 0) s[n] /= p;
}
if(s[n] > 1) ans = min(ans, cal(s[n])); //大质因子别漏了
cout << ans;
}