cf 601 E2. Send Boxes to Alice (Hard Version)

Send Boxes to Alice (Hard Version)
给定 $a_{1}, a_{2}, \dots, a_{n}$ ，求使 $a_{x_{1}} = a_{x_{2}} = \dots = a_{x_{t}} = k ， t = \frac{s u m}{k}$ 的最小花费，其中，k是sum的因子。
显然的，如果 $k_{1} < k_{2}$ ，且 $k_{1} ∣ k_{2}$ ，则 $k = k_{1}$ 时，答案小于 $k = k_{1}$ 时的答案。
所以，枚举因子的时候可以不用枚举因子k的倍数。
所以，题意就是将a中的某一小段中的所有数字加到其中的一个点上，花费为 $d i s * a_{i}$
显然，从左到右，一段区间和大于k，那么这一段区间必然要汇合成一个点。
该段区间花费最小时，汇合的点m坐标满足：
$\sum_{l}^{m - 1} a_{i} + a_{m} > \sum_{m + 1}^{r}$
$\sum_{l}^{m - 1} a_{i} < a_{m} + \sum_{m + 1}^{r}$
显然，m取其他值时，答案更大。
$s u m_{m a x} = 1 0^{12}$ ，sum不同因子数最多为12个。
如何快速计算一个确定的k的答案：
当i<m时， $a n s + = s u m_{l . . . i}$
当i=m时， $a n s + = 0$
当i>m是， $a n s + = s u m_{i . . . r} = s u m_{l . . . r} - s u m_{l . . . i - 1} = k - s u m_{l . . . i - 1}$

for(int i=l;i<=r;++i){
	s=(s+a[i])%k;
	res+=min(s,k-s);
}

代码：

#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*P1=buf,*P2=buf;
#define gc() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<20,stdin),P1==P2)?EOF:*P1++)
#define TT template<class T>inline
TT bool read(T &x){
    x=0;char c=gc();bool f=0;
    while(c<48||c>57){if(c==EOF)return 0;f^=(c=='-'),c=gc();}
    while(47<c&&c<58)x=x*10+c-48,c=gc();
    if(f)x=-x;return 1;
}
TT bool read(T&a,T&b){return read(a)&&read(b);}
TT bool read(T&a,T&b,T&c){return read(a)&&read(b)&&read(c);}
typedef long long ll;
#define Init(a,v) memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
const ll MAXN=1e6+8,mod=1e9+7,inf=0x3f3f3f3f;
ll n,a[MAXN],s;
ll solve(ll k){
    ll pre=0,res=0;
    for(int i=1;i<=n;++i)(pre+=a[i])%=k,res+=min(pre,k-pre);
    return res;
}
int main() {
    read(n);
    for(int i=1;i<=n;++i){
        read(a[i]);
        s+=a[i];
    }
    if(s<=1){printf("-1");return 0;}
    ll ans=1ll<<62,k;
    for(k=2;k*k<=s;++k){
        if(s%k)continue;
        while(s%k==0)s/=k;
        ans=min(ans,solve(k));
    }
    if(s>1)ans=min(ans,solve(s));
    printf("%I64d",ans);
    return 0;
}