[ABC191F] GCD or MIN 题解

SalN · 2023-08-08 19:05:34 · 题解

linkqwq

题目大意

给定 n 个整数 a_1,\dots,a_n，每次选择两个数 x,y 去掉并加入 \gcd(x,y) 或者 \min(x,y)，求最后一个数有多少种取值。

题目解法

只有「删除 x,y 加入 \gcd(x,y)」的情况，答案显然是所有数的 \gcd。

「删除 x,y 加入 \min(x,y)」这种操作我们可以理解成「删去 \max (x,y)」。意思是，对于一个序列，除了 \min\{a_i\} 以外的其它任何数肯定都可以随便被删除。

我们先考虑一个弱化版问题，可以「删除 x,y 加入 \gcd(x,y)」或者「删除 x」。这种情况下，任意滴取一些数算其 \gcd 都是合法的捏，不选的数删除就好了。

我们再考虑加上了「不能删除 \min\{a_i\}」的约束的情况。这个时候，如果算出来的最终值 k>\min\{a_i\} ，此时 \min\{a_i\} 仍然存在（不然怎么比最小值大嘛），无法正常的删除，因为祂不是最小值啊。因为序列的最小值肯定越来越小，所以这种情况不能通过调整顺序和操作来避免。反过来，如果 x\leq \min\{a_i\} 那么显然很合法捏。

我们考虑弱化版问题中一个数 k 可不可以成为最终答案，假设 k 的倍数有 a_{p_1},a_{p_2},...,a_{p_n}。合法序列的 \gcd=k，因为任何的合法序列跟 k 的倍数继续取 \gcd 仍然是 k，所以 \gcd\{a_{p_i}\}=k 相当于 k 就合法。实际算的时候枚举 a_i 的约数就可以做到 O(\sum\sqrt a_i) 了。

具体而言，用 g[t_0] 表示 t_0 的倍数的 \gcd。对于每一个 a_i 枚举其因数 t，使得 g[t]=\gcd(g[t],a_i)，最后算 g[t_0]=t_0(t_0\leq\min\{a_i\}) 的个数即可。复杂度 O(n\sqrt a_i)，map 的话再带一个 \log。

#include<bits/stdc++.h>

using namespace std;

const int N=2023, inf=1e9;
int n, a[N], m=inf, ans;
map<int,int> g;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i];
        m=min(a[i],m);
    }
    for(int i=1; i<=n; ++i)
        for(int j=1; j*j<=a[i]; ++j)
            if(a[i]%j==0) {
                g[j]=__gcd(g[j],a[i]);
                g[a[i]/j]=__gcd(g[a[i]/j],a[i]);
            }
    map<int,int>::iterator it;
    for(it=g.begin(); it!=g.end(); ++it)
        if(it->first<=m) ans+=(it->first==it->second);
    cout << ans;
    return 0;
}