HDU – 6237 A Simple Stone Game (质因数分解+思维)

• 计算出a[i] % x的值r[i]，将其排序（升序或降序皆可），然后以r[i]的值计算前缀和pr，x-r[i]的值计算后缀和su
• 中间必定有一个状态，pr[i] = su[i+1]
• 找到这个状态，加上pr[i]即可

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const ll INF = 1e18;
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
    (A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
    (A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
inline void outt(int x) {
    if(x>9) outt(x/10);
    putchar(x%10+'0');
}
const int maxn = 1e5+10;

ll a[maxn];
ll r[maxn];

ll su[maxn];
ll pr[maxn];

vector<ll>v;
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        v.clear();
        ll n;
        cin>>n;
        ll sum = 0;
        ll maxx = 0;
        rep(i,1,n)cin>>a[i],sum += a[i], maxx=max(maxx,a[i]);
        ll sss = sum;
        for(ll i=2; i*i<=sum; ++i) {
            if(sum%i==0) {
                v.push_back((ll)i);
                while(sum%i==0) {
                    sum /= i;
                }
            }
        }
        if(sum>1) v.push_back(sum);
        if(n==1){
            puts("0");
            continue;
        }
        ll ans = sss - maxx;
        for(ll i=0; i<v.size(); ++i) {
            ll tmp = 0;
            rep(j,1,n) {
                r[j] = a[j] % v[i];
            }
            sort(r+1,r+n+1);
            su[n+1] = 0;
            pr[0] = 0;
            rep(j,1,n){
                pr[j] = pr[j-1] + r[j];
            }
            per(j,1,n){
                su[j] = su[j+1] + (v[i]-r[j])%v[i];
            }
            rep(j,1,n-1){
                if(pr[j] == su[j+1]){
                    ans = min(ans,pr[j]);
                    break;
                }
            }
//            ll ed = n;
//            ll st = 1;
//            while(st<=ed) {
//                while(st<=ed&&r[st] >= v[i]-r[ed]) {
//                    tmp += v[i]-r[ed];
//                    r[st] -= v[i]-r[ed];
//                    ed--;
//                }
//                if(r[st]>0) {
//                    r[ed] += r[st];
//                    tmp += r[st];
//                }
//                st++;
//            }
//            ans = min(ans, tmp);
        }
        cout<<ans<<endl;
    }

    return 0;
}