题：

Doge与石子游戏

题目描述

$Doge$ 最近迷上了一个新游戏，有 $n$ 堆石子，每堆有 $a_i$ 个石子，对于每一次操作，$Doge$ 可以将某堆的一个石子移动到另外一堆。游戏终止的条件是：存在一个 $x(x>1)$ ，使得任意一堆石子均满足：$a_i\%x==0(1\le i\le n)$

$Doge$ 认为这个游戏挺无聊的，所以他现在想早点结束这个游戏，请你告诉他游戏终止所需要的最少操作次数。

输入格式

第一行一个数，表示 $n(n>0)$

第二行有 $n$ 个数，表示每一堆石子的个数 $(0\le a_i\le 10^5)$

输出格式

一个数，表示最少的操作次数

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

2

提示

样例解释

第一步，$Doge$ 把第一堆的一个石子移到第二堆，此时为 $0,3,3,4,5$

第二步，$Doge$ 把第四堆的一个石子移到第五堆，此时为 $0,3,3,3,6$

当 $x=3$ 时，满足游戏终止条件，故步数为 $2$

Hints

对于 $30\%$ 的数据，满足 $n\le 20$

对于 $100\%$ 的数据，满足 $n\le 10^5$

Code :

//T2.cpp
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int INF = 0x7fffffff;

int n, a[N], b[N];
ll sum = 0, ans = INF;

bool cmp(int lhs, int rhs) {return lhs > rhs;}

signed main() {
	
	cin >> n; for(int i = 1; i <= n; ++i) { cin >> a[i]; sum += a[i]; }
	
	for (int x = 2; x <= sqrt(sum); ++x) { 
		if (sum % x != 0) continue;
		
		int cnt = 0;	
		for (int i = 1; i <= n; ++i) b[i] = a[i] % x;
		for (int i = 1; i <= n; ++i) cnt += b[i];
		sort(b + 1, b + n + 1, cmp);
		
		int k = cnt / x;
		
		int i = 1;
		while (i <= n && b[i] != 0) ++i;
		
		int tmp = 0;
		for (int j = k + 1; j < i; ++j) tmp += b[j];
		
		ans = min(ans, (ll)tmp);
	}
	if (ans == INF) {
		cout << 0;
	}else cout << ans;
	return 0;
}