526互联

Codeforces Global Round 24 B. Doremy's Perfect Math Class

发布时间 2023-09-05 21:29:00作者: zsxuan

给一个元素个数为 \(n\) 的正整数集合 \(S\) ，可以做以下操作任意次：

  • 选择 \(S\) 中的两个元素 \(x\) \(y\) 满足 \(x > y\) 且 \(x - y\) 不在集合内。
  • 加入 \(x - y\) 到集合。

经过若干次操作后，集合中最多能存在多少元素。

性质一：两个数 \(x\) \(y\) 辗转相减，最后能得到的最小数为 \(gcd(x, y)\) 。（可以构造证明。且这是常识，平时不会比赛也不可能临时通过构造证明）

性质二：\(gcd(x, y) | x - y\) ，辗转相减过程中的 \(x'\) \(y'\) 依旧是 \(gcd(x, y)\) 的倍数。

性质三：集合 \(S\) 所有数辗转相减，能得到的最小数为 \(gcd(S_1, S_2, \cdots, S_m)\) 。

令开始 \(S\) 的 \(gcd\) 为 \(g\) ，显然 \(0\) 无法在辗转相减中得到，则集合最大时为 \(g， 2g, 3g, \cdots, S_{max}\) 。

于是 \(|S|_{max} = \frac{S_{max}}{g}\) 。

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);
	int g = 0, mx = 1;
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		g = gcd(g, a[i]);
		mx = std::max(mx, a[i]);
	}
	std::cout << mx / g << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}