A Simple Stone Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1247 Accepted Submission(s): 287
Problem Description
After he has learned how to play Nim game, Bob begins to try another stone game which seems much easier.
The game goes like this: one player starts the game with N piles of stones. There is ai stones on the i th pile. On one turn, the player can move exactly one stone from one pile to another pile. After one turn, if there exits a number x(x>1) such that for each pile bi is the multiple of x where bi is the number of stone of the this pile now), the game will stop. Now you need to help Bob to calculate the minimum turns he need to stop this boring game. You can regard that 0 is the multiple of any positive number.
The game goes like this: one player starts the game with N piles of stones. There is ai stones on the i th pile. On one turn, the player can move exactly one stone from one pile to another pile. After one turn, if there exits a number x(x>1) such that for each pile bi is the multiple of x where bi is the number of stone of the this pile now), the game will stop. Now you need to help Bob to calculate the minimum turns he need to stop this boring game. You can regard that 0 is the multiple of any positive number.
Input
The first line is the number of test cases. For each test case, the first line contains one positive number N(1≤N≤100000)
, indicating the number of piles of stones.
The second line contains N positive number, the i th number ai(1≤ai≤100000) indicating the number of stones of the i th pile.
The sum of N of all test cases is not exceed 5∗105 .
The second line contains N positive number, the i th number ai(1≤ai≤100000) indicating the number of stones of the i th pile.
The sum of N of all test cases is not exceed 5∗105 .
Output
For each test case, output a integer donating the answer as described above. If there exist a satisfied number x
initially, you just need to output 0
. It's guaranteed that there exists at least one solution.
Sample Input
2
5
1 2 3 4 5
2
5 7
Sample Output
2
1
Source
铜牌题坑就是多呀，注意读懂题意，sum是会爆int的，还有sum本身就有可能是个素数，其他的就没啥坑了。
解题思路：求出石子总数sum，能整除sum的质数肯定满足x，遍历1-1e5的所有质数，统计满足x的有多少个。然后遍历满足x的质数，求出最小的移动次数，与sum减去最大堆（sum为质数的情况）的值作比较，取小的便是最终答案。具体操作看代码，代码比文字好理解(●'◡'●)
1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include <cstdio> 5 using namespace std; 6 typedef long long ll; 7 const int maxn = 1e5+10; 8 int nu[maxn]; 9 int prim[maxn]; 10 bool isprim[maxn]; 11 int res[maxn]; 12 int cop[maxn]; 13 int len; 14 void euler(int maxx) 15 { 16 memset(isprim,true,sizeof(isprim)); 17 isprim[1]=false; 18 len=0; 19 for(int i=2;i<=maxx;++i) 20 { 21 if(isprim[i]) prim[++len]=i; 22 for(int j=1;j<=len && i*prim[j]<=maxx;++j) 23 { 24 isprim[i*prim[j]]=false; 25 if(i%prim[j]==0) break; 26 } 27 } 28 } 29 int main() 30 { 31 euler(1e5); 32 int t; 33 scanf("%d",&t); 34 while(t--) 35 { 36 int n; 37 scanf("%d",&n); 38 ll sum=0; 39 for(int i=0;i<n;++i) 40 { 41 scanf("%d",&nu[i]); 42 sum+=nu[i]; 43 } 44 sort(nu,nu+n); 45 ll ans = sum-nu[n-1]; 46 int le=0; 47 for(int i=1;i<=len;++i) 48 { 49 if(sum%prim[i]==0) 50 { 51 res[++le]=prim[i]; 52 while(sum%prim[i]==0) 53 sum/=prim[i]; 54 } 55 } 56 57 for(int i=1;i<=le;++i) 58 { 59 // printf("%di ",res[i]); 60 for(int j=0;j<n;++j) 61 { 62 cop[j]=nu[j]%res[i]; 63 // printf("%d ",cop[j]); 64 } 65 sort(cop,cop+n); 66 ll cnt=0; 67 int l=0,r=n-1; 68 while(l<r) 69 { 70 // printf("@"); 71 if(cop[l]==0) 72 { 73 l++; 74 continue; 75 } 76 if(cop[l]+cop[r]==res[i]) 77 { 78 cnt+=cop[l]; 79 // printf(" %d## ",cnt); 80 l++; 81 r--; 82 } 83 else if(cop[l]+cop[r]<res[i]) 84 { 85 cop[r]+=cop[l]; 86 cnt+=cop[l]; 87 l++; 88 } 89 else if(cop[l]+cop[r]>res[i]) 90 { 91 cnt+=res[i]-cop[r]; 92 cop[l]-=(res[i]-cop[r]); 93 r--; 94 } 95 } 96 // printf(" %d## ",cnt); 97 ans=min(cnt,ans); 98 // printf(" %d### ",ans); 99 } 100 printf("%lld ",ans); 101 } 102 return 0; 103 }