P10443 「MYOI-R3」消消乐 题解

· · 题解

传送门

这个其实很水的思维题，但我赛时却想了 50 分钟。

将数组 x 从小到大排序。

很显然，根据 \gcd(a,b) \le \min(a,b)，就可以发现 x_n 和 x_{n-1} 一定不会被删去。那么数组 x 想进行 x-2 此操作就必须将 x_1 \cdots x_{n-2} 都删去。

继续，我们现在想把 x_1 \cdots x_{n-2} 都删去。

那么此时，x_{n-2} 和 x_{n-3} 就是最大的了，最后肯定会剩下他俩，那么他俩想被约去，就必须是 \gcd(x_n,x_{n-1})。同理可得：那前面的数想被约掉，就必须得是 \gcd(x_{n-2},x_{n-3})=\gcd(\gcd(x_n,x_{n-1}),\gcd(x_n,x_{n-1}))=\gcd(x_n,x_{n-1})。

那么可得：这个数组 x 能进行 n-2 此操作，当且仅当任意一个 i（1 \le i \le n-2）皆满足 x_i=\gcd(x_n,x_{n-1})。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 III;
const db eqs=1e-6;
const int inf=1e9;
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}

const int MAXN=1000000+5;
int T,n,a[MAXN];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        if(n==2) 
        {
            cout<<"Yes\n";
            continue;
        }
        bool flag=1;
        for(int i=1;i<=n-2;i++)
        {
            if(a[i]!=__gcd(a[n],a[n-1]))
            {
                cout<<"No\n";
                flag=0;
                break;
            }
        }
        if(flag) cout<<"Yes\n";
    }   
    return 0;
}