題干：

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?NN?piles of stones. There is?aiai?stones on the?iith 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)x(x>1)?such that for each pile?bibi?is the multiple of?xx?where?bibi?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?00?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)N(1≤N≤100000), indicating the number of piles of stones.

The second line contains?NN?positive number, the?iith number?ai(1≤ai≤100000)ai(1≤ai≤100000)?indicating the number of stones of the?iith pile.


The sum of?NN?of all test cases is not exceed?5?1055?105.

Output

For each test case, output a integer donating the answer as described above. If there exist a satisfied number?xx?initially, you just need to output?00. 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

題目大意：

玩一個游戲，有n堆石頭，每堆石頭有a[i]個，每次你能將一堆石頭的一個放到其他堆，當存在一個x使得所有的a[i]%x==0,游戲結(jié)束，輸出游戲進行的最小次數(shù)。（n,a[i]<=1e5）

解題報告：

首先這個x可以進行縮減，如果x的倍數(shù)是可以的，那x一定是可以的，也就是說我們只需要考慮x是質(zhì)數(shù)就可以了。

那么1e5個數(shù)，每個數(shù)的質(zhì)因子還是特別的多的，其實我們也不需要考慮這么多數(shù)字，想想他既然有解，說明他x一定可以整數(shù)所有數(shù)，所以我們不需要分別看這n個數(shù)，只需要看看，這n個數(shù)的和就可以了。不難發(fā)現(xiàn)這個和<=1e10，所以我們可以先求和，然后對和進行質(zhì)因子分解（不超過10個），然后枚舉這些質(zhì)因子。

對于接下來的處理，首先對枚舉的這個數(shù)x取模一下，因為剩下的那些數(shù)都是沒啥用的，然后可以貪心構(gòu)造，每次都讓小的摞到高的上，這樣一定可以保證移動次數(shù)最少，其實不難發(fā)現(xiàn)不可能存在某一堆中移動>x個石子到另一堆上，因為這樣相當于沒有省略，所以其中x那一部分可以不用挪動，又因為保證有解，所以一定是可以移動過去的。另一種方法是因為給定了總和，給定了x，我們就知道最終要湊出幾個堆來，假設(shè)需要湊出k堆，所以我們對%x后的值排個序，可以貪心選取前k大的元素，看還需要湊多少出來即可。（代碼實現(xiàn)沒有討論的這么麻煩，但是感覺這題還是需要一個嚴謹?shù)乃季S過程的wjhnb）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e5 + 5; bool is[MAX]; ll a[MAX],b[MAX]; int cnt; ll prime[MAX],ans; void init() {memset(is,1,sizeof is);is[1]=is[0]=0;for(int i = 2; i<MAX; i++) {if(is[i] == 0) continue;prime[++cnt] = i;for(int j = i+i; j<MAX; j+=i) is[j]=0;} } vector<ll> vv; void fj(ll x) {for(int i = 1; i<=cnt; i++) {if(x % prime[i] == 0) {vv.pb(prime[i]);while(x%prime[i] == 0) x /= prime[i];}}if(x>1) vv.pb(x); } int main() {init();int T,n;cin>>T;while(T--) {scanf("%d",&n);ll sum = 0;vv.clear();ans=1e18;for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum += a[i];fj(sum);for(auto x : vv) {ll tmp = 0,tt=0;for(int i = 1; i<=n; i++) {b[i] = a[i]%x;tt += b[i];}sort(b+1,b+n+1);ll zu = tt/x;for(int i = n; i>=n-zu+1; i--) tmp += x - (b[i]);ans = min(ans,tmp); }printf("%lld\n",ans);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 6237】A Simple Stone Game（贪心，思维，素因子分解，数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。