526互联

Educational Codeforces Round 110 (Rated for Div. 2) Array Reodering

发布时间 2023-10-10 14:45:06作者: zsxuan

给一个长为 \(n\) 的数组 \(a\) 。

定义一对 \(pair(i, j)\) 是 \(good\) 的当且仅当 \(1 \leq i < j \leq n\) 且 \(gcd(a_i, 2 \cdot a_j) > 1\) 。

如果你可以以任意顺序重排数组 \(a\) ，找到最多的 \(good\) 对数。

观察 \(gcd(a_i, 2 \cdot a_j)\) ，相当于若 \(a_i \equiv 0 (\mod 2)\) 即可让 \(a_i\) 和右边的任意 \(a_j\) 配对。

贪心地让 \(\mod 2 = 0\) 的元素排在左边 \([1, l]\) ， \(\mod 2 = 1\) 的元素排在右边 \([l + 1, n]\) 。可以使 \([1, l]\) 的所有元素都和右边任意一个元素配对。

而 \([l + 1, n]\) 中的所有元素不存在因子 \(2\) 。于是 \(gcd(a_i, 2 \cdot a_j) > 1\) 当且仅当 \(gcd(a_i, a_j) > 1\) 。此时枚举所有 \((i, j)\) 对即可。

\(ans = \sum_{i = 1}^{l} n - i + \sum_{i = l + 1}^{n}\sum_{j = i + 1}^{n} [gcd(i, j) > 1]\) 。

view 
#include <bits/stdc++.h>
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	std::sort(a.begin() + 1, a.end(), [&](int x, int y){
		return x % 2 < y % 2;
	});
	
	int L = 1;
	while (L <= n && a[L] % 2 == 0) L++;
	L -= 1;
	
	// n-1 n-2 ... n-L -> sum = L * (2n - L - 1) / 2
	long long ans = 1LL * L * (2LL * n - L - 1) / 2;
	
	for (int i = L + 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ans += (gcd(a[i], a[j]) > 1);
		}
	}
	std::cout << ans << '\n';
}
		                
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}