HDU6237 A Simple Stone Game(貪心+質因子分解)

HDU6237

前面都不難想,令

s

u

m

n

=

∑

a

i

sumn=\sum a_i

sumn=∑ai​

設最後

g

c

d

x

gcd=x

gcd=x,

x

x一定是

sumn

sumn的因子

而且

x一定是質因子(

gcd

gcd)

那麼

sumn最多有

30

30多個不同的質因子

可以枚舉

gcd來計算最小代價

确定了

gcd後,怎樣移動石子最劃算??

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int t,n,a[maxn];
vector<int>vec,rw;
signed main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n; 
		vec.clear();
		int sumn=0,ans=1e18;
		for(int i=1;i<=n;i++)	cin >> a[i],sumn += a[i];
		for(int i=2;i*i<=sumn;i++)
		{
			if( sumn%i==0 )	vec.push_back(i);
			while( sumn%i==0 )	sumn/=i;
		}
		if( sumn>1 )	vec.push_back(sumn);
		sort( vec.begin(),vec.end() );
		for(int i=0;i<vec.size();i++)
		{
			int temp=0;
			rw.clear();
			for(int j=1;j<=n;j++)
			{
				temp += a[j]%vec[i];
				if( a[j]%vec[i] )	rw.push_back( a[j]%vec[i] );	
			}
			sort( rw.begin(),rw.end() );
			int cnt=0;
			for(int j=rw.size()-1;j>=0;j--)
			{
				cnt += vec[i]-rw[j];
				temp -= vec[i];
				if( temp<=0 )	break;
			}
			ans = min( ans,cnt );
		}
		cout << ans << '\n';
	}
}