n堆石子 每次只能拿一个石子从一堆移到另一堆 知道所有的堆的石子数目都能整除x(x>1) 问最小移动次数
枚举x的可能取值 即a[i]和的素因子即可 合因子的区间变化会比较大 然后求余 每次都把石子移到余数最大的那一堆，加起来的总和求最小值。
注意 开longlong
1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <iostream> 6 #include <sstream> 7 #include <algorithm> 8 #include <string> 9 #include <queue> 10 #include <ctime> 11 #include <vector> 12 using namespace std; 13 const int maxn= 1e5+5; 14 const int maxm= 1e6+5; 15 const int inf = 0x3f3f3f3f; 16 typedef long long ll; 17 ll su[maxm]; 18 int a[maxn],b[maxn]; 19 int cnt,n; 20 void sushu(ll x) 21 { 22 cnt=0; 23 for(int i=2;i<=sqrt(x);i++) 24 { 25 if(x%i==0) 26 su[cnt++]=i; 27 while(x%i==0) 28 x/=i; 29 } 30 su[cnt++]=x; 31 } 32 int cmp(int a,int b) 33 { 34 return a>b; 35 } 36 int main() 37 { 38 int t; 39 scanf("%d",&t); 40 while(t--) 41 { 42 scanf("%d",&n); 43 ll sum=0; 44 for(int i=0;i<n;i++) 45 { 46 scanf("%d",&a[i]); 47 sum+=a[i]; 48 } 49 sushu(sum); 50 ll maxx=99999999999; 51 for(int i=0;i<cnt;i++) 52 { 53 ll sum=0,cont=0; 54 for(int j=0;j<n;j++) 55 { 56 b[j]=a[j]%su[i]; 57 sum+=b[j]; 58 } 59 sort(b,b+n,cmp); 60 int k=0; 61 while(sum!=0&&k<n) 62 { 63 cont+=su[i]-b[k++]; 64 sum-=su[i]; 65 } 66 maxx=min(maxx,cont); 67 } 68 printf("%lld ",maxx); 69 } 70 }