题目链接: A Simple Stone Game

大致题意

给定 n n n堆石子, 第 i i i堆有 a i a_i ai​个.

你可以执行任意次操作, 每次选择编号为 i i i和 j j j的石子堆, 表示把一个石子从第 i i i堆挪到第 j j j堆.

问: 至少执行多少次操作, 才能使得 g c d ( { a 1 , a 2 , . . , a n } ) > 1 gcd(\{ a_1, a_2, .., a_n \}) > 1 gcd({a1​,a2​,..,an​})>1

解题思路

思维

我们简化一下题意, 相当于最后 a 1 , a 2 , . . , a n a_1, a_2, .., a_n a1​,a2​,..,an​都有公因子 x x x. ( x x x可以是 g c d ( { a 1 , a 2 , . . , a n } ) gcd(\{ a_1, a_2, .., a_n \}) gcd({a1​,a2​,..,an​})的因子)

可以证明, 我们只需要枚举所有的 x ∈ { 质 数 } x \in \{ 质数 \} x∈{质数} 即可.

因为如果公因子 x x x不是质数, 可以写成 x = p 1 k 1 ⋅ p 2 k 2 . . . x = p_1^{k_1} · p_2^{k_2}... x=p1k1​​⋅p2k2​​...的形式, 我们枚举 p i p_i pi​同样是合法的, 且是更优的.

---

设 s u m = ∑ i − 1 n a i sum = \displaystyle\sum_{i - 1}^na_i sum=i−1∑n​ai​, 我们只需要检查 s u m sum sum的所有质因子即可.

对于每个质因子 p p p而言, 我们可以设 b [ ] b[] b[], 其中 b i = a i b_i = a_i % p bi​=ai​, 表示 a i a_i ai​需要移除多少个石子才能有因子 p p p.

我们较容易想到, 如果对于某个 b i b_i bi​而言, 如果比较小, 我们从这堆移出石子到其他堆更优, 反之应当把石子移入当前堆.

因此我们不妨对于 b [ ] b[] b[]从小到大排序, 用双指针 l = 1 , r = n l = 1, r = n l=1,r=n来表示, 我需要从第 l l l堆移石子到第 r r r堆.

可以保证最后一定可以使得 ∀ b i % p = 0 \forall b_i \% p = 0 ∀bi​%p=0.

因为sum % p = 0, 则 ∑ i − 1 n b i   %   p = 0 \displaystyle\sum_{i - 1}^nb_i \ \% \ p = 0 i−1∑n​bi​ % p=0 必然成立.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
int n;
int a[N], b[N];
ll fact(ll p) {
	ll all = 0;
	rep(i, n) b[i] = a[i] % p, all += b[i];
	sort(b + 1, b + 1 + n);

	ll res = 0;
	for (int l = 1, r = n; l < r; ++l) {
		if (!b[l]) continue;

		while (b[l]) {
			ll qaq = min<ll>(b[l], p - b[r]);
			b[l] -= qaq, b[r] += qaq;
			res += qaq;

			if (b[r] == p) r--;
		}
	}
	return res;
}
int main()
{
	int t; cin >> t;
	while (t--) {
		scanf("%d", &n);
		ll all = 0;
		rep(i, n) scanf("%d", &a[i]), all += a[i];

		ll res = LLONG_MAX;
		for (int p = 2; p <= all / p; ++p) {
			if (all % p == 0) {
				while (all % p == 0) all /= p;

				res = min(res, fact(p));
			}
		}
		if (all > 1) res = min(res, fact(all));

		printf("%lld\n", res);
	}
	return 0;
}

END