冬之花

dottle · 2022-09-05 19:13:51 · 题解

如果说我们有 2 个不同的数可以用来操作，那么无论当前的 x 是多少，都总有一个数操作以后不会使 x 变为 0。这时候答案就一定是 Yes。

接下来的问题就变成了，如果所有数都相同，是否能进行 10^{100} 次操作。如果初始的 x 和 a_1 符号相同，那么无论如何 x 都不会变成 0；如果 x 不是 a_1 的倍数，那么 x 也不可能变成 0。这两个情况答案都是 Yes。对于剩下的情况，即 x 与 a_1 符号相反，且 x 是 a_1 的倍数，答案就是 No 了。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n,x;cin>>n>>x;
    int first;cin>>first;
    int flag=0;
    for(int i=2;i<=n;i++){
        int now;cin>>now;
        if(now!=first)
            flag=1;
    }
    if(flag){
        cout<<"Yes"<<endl;
        return ;
    }
    if(x%first!=0){
        cout<<"Yes"<<endl;
        return ;
    }
    if(x/first>0){
        cout<<"Yes"<<endl;
        return ;
    }
    cout<<"No"<<endl;
}

main(){
    int _T=1;cin>>_T;
    while(_T--)solve();
}