ABC191F_牛客博客

一个可以观察的特性是 $gcd(x,y)<=min(x,y)$ ,所以先找出每个数的因子，其实不难看出，min操作的结果就是删去一个数。且只有最小值不能被删去.且gcd的操作也是单调递减的。所以最后这个数的大小一定小于等于 $min\{a_i\}$
所以问题可以转化为：让你从n个数中选取出一个子集gcd。问你有多少种结果 ≤ $min\{a_i\}$
注：因为我们一旦从一个子集中gcd出一个 ≤ $min\{a_i\}$ 的数。接下来就是把他们全min起来。这样就可以实现上述效果了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 2e3 + 10;
//int a[N];
int n;
int main(){
    map<ll,vector<ll>>q;
    cin >> n;
    ll d = 1e9;
    for(int i=1;i<=n;i++){
        ll x;
        cin >> x;
        d = min(d,x);
        for(ll j = 1;j * j <= x;j++){
            if(x % j == 0){
                q[j].push_back(x);
                if(j * j != x) q[x/j].push_back(x);
            }
        }
    }
    int ans = 0;
    for(auto g:q){
        if(g.first > d) break;
        ll gcd = g.second[0];
        for(auto k:g.second) gcd = __gcd(gcd,k);
        if(gcd == g.first) ans++;
    }
    cout << ans <<  endl;
    return 0;
}