Hdu6237分解质因数

我觉得这道题挺有意思的，很多人把这道题标签设置欧拉函数，不是很理解。。

2017ccpc哈尔滨数论题

题意：

现在有n堆石子，且已知每堆石子的数量，每次操作你可以从任一堆中取一颗石子放到另一堆中，问最少操作几次使得每一堆石子的数量均是某一个数的倍数。即n个数都有一个公因子,a[i]%x==0 (x > 1)

思路：

求出所有数之和sum，显然x一定要是sum的约数，并且最优解时x一定可以是质数

显然这样的x最多不超过30个，所以可以暴力枚举所有满足上述条件的x

处理的时候算出所有的b[i] = a[i]-a[i]/x*x

然后将b[]从大到小排序，遍历一遍就可以得出当前最小移动次数

所有移动次数中取最小就是答案

代码：

 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-18 16:39:45
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define int long long 
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int n,sum,cnt;
int a[maxn],b[maxn],prime[100];

void get_prime(int x){
	memset(prime,0,sizeof(prime));
	cnt = 0;
	int maxx = sqrt(x);
	for(int i = 2; i <= maxx; i++){
		if(x%i==0)prime[cnt++] = i;
		while(x&&((x%i)==0)){
			x /= i;
		}
	}
	if(x > 1)prime[cnt++] = x;
}

main()
{
	int t ;
	cin >> t;
	while(t--){
		cin >> n;
		sum = 0;
		for(int i = 1; i <= n;i++){
			scanf("%lld",&a[i]);
			sum += a[i];
		}
		get_prime(sum);
		int ans = linf;
		for(int i = 0; i < cnt;i++){
			int min_ = 0;
			int zz = 0;
			for(int k = 1; k <= n;k++){
				b[k] = a[k] % prime[i];
				zz += b[k];
			}
			if(zz % prime[i] != 0)continue;
			sort(b+1, b+n+1, greater<int >());
			for(int k = zz / prime[i] +1; k <= n;k++){
				min_ += b[k];
				if(b[k] == 0)break;
			}
			ans = min(ans, min_);
		} 
		cout << ans << endl;
	}
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/