Codeforces Global Round 24 B. Doremy's Perfect Math Class
给一个元素个数为 \(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;
}