P10443 「MYOI-R3」消消乐

Koei · 2025-10-01 21:57:00 · 个人记录

P10443 「MYOI-R3」消消乐

题目要求：

若 \gcd(a_x,a_y)=a_z 则删除 a_z 且 x\ne y \ne z

说白了就是将删掉数组中存在的任意两数的gcd

注意到：

通过gcd的性质我们可以发现 gcd(x,y)\le min(x,y) 所以数组中的最大值和次大值 max(a_i)\text{ }\text{ } and \text{ }\text{ }next-max(a_i)

所以，如果其余的 n-2 个数都是 gcd(max(a_i)\text{ } , \text{ }next-max(a_i)) 则输出 Yes，否则又如何一个不是就输出 No.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e6+10);
int n,T;
int a[maxn];
int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        bool flag(false);
        for(int i(1);i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        if(n==2){
            cout<<"Yes\n";
            continue;
        }
        int gd(gcd(a[n],a[n-1]));
        for(int i(1);i<n-1;i++){
            if(a[i]!=gd){
                cout<<"No\n";
                flag=true;
                break;
            }
        }
        if(!flag){
            cout<<"Yes\n";
        }
    }
    return 0;
}