我们考虑前缀和sum[i],如果将a[i+1]中的一个塞入a[i]中,则不影响sum[i+1],但是sum[i]++,如果将a[i]中的一个塞入a[i+1],则不影响sum[i+1],但是sum[i]--,我们可以发现操作一次相当于将一个sum[i]+1或者到sum[i]-1,那么题意就变成了操作多少次可以使得所有的sum[i]为某一个k的倍数,那么一个sum[i]变成k的倍数操作次数最小必然为min(sum[i]%k,k-sum[i]%k),那么接下如何考虑k呢,显然k是sum[n]的一个因子,否则必然不可能,但是sum[n]范围1e12,枚举所有因子高达212个,显然不行,但是其实我们只需要枚举质因子即可,可以得出结论他的质因子所得的操作次数最小值必然不超过k所得的操作数。总体复杂度O(12n)。
1 // ——By DD_BOND 2 3 #include<bits/stdc++.h> 4 5 #define pb push_back 6 7 using namespace std; 8 9 typedef long long ll; 10 11 const ll LLMAX=2e18; 12 const int MAXN=1e6+10; 13 14 vector<ll>prime; 15 ll a[MAXN],sum[MAXN]; 16 17 int main(void) 18 { 19 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 20 ll n,ans=LLMAX; cin>>n; 21 for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i]; 22 if(sum[n]==0) return cout<<0<<endl,0; 23 if(sum[n]==1) return cout<<-1<<endl,0; 24 ll p=sum[n]; 25 for(ll i=2;i*i<=sum[n];i++) 26 while(p%i==0){ 27 prime.pb(i); 28 p/=i; 29 } 30 if(p!=1) prime.pb(p); 31 prime.erase(unique(prime.begin(),prime.end()),prime.end()); 32 for(auto i:prime){ 33 ll cur=0; 34 for(int j=1;j<=n;j++) cur+=min(sum[j]%i,i-sum[j]%i); 35 ans=min(ans,cur); 36 } 37 cout<<ans<<endl; 38 return 0; 39 }