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\n",maxx);
69 }
70 }