Codeforces 687 B

​​傳送門​​

題目大意

思路

代碼

bool vis[maxn];//标記非素數,0是素數
int primer[maxn/10];//存素數
int cnt=0;//記錄素數個數，
void find_primer(){
    for(int i=2;i <=maxn;i++){
        if(!vis[i])primer[cnt++]=i;
        for(int j=0;j<cnt&&primer[j]*i<=maxn;j++){
            vis[i*primer[j]]=1;//篩
            if(i%primer[j]==0)break;//關鍵！！！找到i*primer[j]的最小質因子primer[j]，退出
        }
    }    
}
map<int,int>mp;
void init(int x){
    for(int i=0;primer[i]*primer[i]<=x;i++){
        if(x%primer[i]==0){
            int cnt1=0;
            while(x%primer[i]==0){
                cnt1++;
                x/=primer[i];
            }
            mp[primer[i]]=max(mp[primer[i]],cnt1);
        }
    }
    if(x>1)mp[x]=max(mp[x],1);
}

int main(){
    scanf("%d%d",&n,&k);
    find_primer();
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        init(c[i]);
    }
    int flag=1;
    for(int i=0;primer[i]*primer[i]<=k&&i<cnt;i++){
        if(k%primer[i]==0){
            int cnt1=0;
            while(k%primer[i]==0){
                k/=primer[i];
                cnt1++;
            }
            if(mp[primer[i]]<cnt1){
                flag=0;
                break;
            }
        }
    }
    if(k>1){
        if(mp[k]<1){
            flag=0;
        }
    }
    if(flag){
        puts("Yes");
    }
    else{
        puts("No");
    }
}