题目分析
我们发现，\(\text{min}\) 操作实际上就是把两数当中较大的那个删除，较小的那个数不受影响，所以用最小的数删还是用另一个数删是无区别的。
一个性质：
\[\gcd(x,y) \le \min(x,y) \]不管 \(a_{min}\) 是原来的还是在 \(\text{gcd}\) 操作后新生成的，所以无论什么时候删，该删的数都能删掉。
问题简化为：取一些数的 \(\text{gcd}\)，然后用最小的数删，删到只剩一个 \(\text{gcd}\)。
所以我们只需要求去除子集最大公因数的个数即可。那么对于每个 \(a_i\) 都分解因数，对于每个因数，记录有哪些 \(a_i\) 包含它。然后再遍历一遍，比对此因数是否与其对应的 \(a_i\) 最大公因数相等即可。
贴上代码
#include<bits/stdc++.h>
// #define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("YES")
#define no puts("NO")
#define inf 1e9
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=2010;
int n;
int ans;
int a[maxn];
map<int,int> mp;
inline void init(){
n=read();
for(register int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
}
int main(){
init();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=sqrt(a[i]);++j){
if(a[i]%j==0){
if(j<=a[1]) mp[j]=__gcd(mp[j],a[i]);
if(a[i]/j<=a[1]) mp[a[i]/j]=__gcd(mp[a[i]/j],a[i]);
}
}
}
map<int,int>::iterator it;
for(it=mp.begin();it!=mp.end();++it){
if(it->first==it->second) ans++;
}
printf("%d\n",ans);
}