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

CPP

#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;
}

P10443 「MYOI-R3」消消乐

文章操作

P10443 「MYOI-R3」消消乐

题目要求：

注意到：

相关推荐

评论

P10443 「MYOI-R3」消消乐