算法
(数论、思维)
记最后剩下的数为 $k$,$L = \min\{A_i\}$
注意到,对于 $x, y \geqslant 1$,有 $\gcd(x, y) \leqslant \min(x, y)$,所以 $k \leqslant L$
此外,$k$ 必须是 $A$ 序列中某个子集的 GCD
所以,我们只需统计 $1 \sim L$ 之中有多少个数 $x$ 满足存在某个子集的 GCD
等于 $x$ 即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
map<int, int> mp;
int l = 1e9;
auto add = [&](int a, int x) {
int p = mp[x];
mp[x] = gcd(a, p);
};
rep(i, n) {
for (int j = 1; j * j <= a[i]; ++j) {
if (a[i]%j == 0) {
add(a[i], j);
add(a[i], a[i]/j);
}
}
l = min(l, a[i]);
}
int ans = 0;
for (auto [x, g] : mp) {
if (x <= l and g == x) ++ans;
}
cout << ans << '\n';
return 0;
}