学步园

题目描述

给你一个有N个数的集合S和一个数X，判断是否存在S的一个子集，子集里的数的最小公倍数正好是X。

输入

第一行是数据组数T。 接下来有多组数据，每组数据包含两行： 第一行有2个数N和X，1<=N<=100000 ，X<=10^9。 第二行给出N个数，1<=S[i]<=10^9。

输出

对于每一组数据，输出一行"Case #X: Y"，X是第几组数据，Y是Yes或No。

样例输入

2
4 20
2 3 4 5
3 61
3 4 5

样例输出

Case #1: Yes
Case #2: No

Source

HL 

#include<stdio.h>
int main()
{
    int n,x,a[100005],aa,max,t,tm,flog,j,i,k;
    scanf("%d",&t);
    tm=t;
    while(t--)
    {
        scanf("%d%d",&n,&x);
        max=0; flog=0;k=0;
        for( i=0; i<n; i++)
        {
            scanf("%d",&aa);
            if(x%aa==0)//缩小集合
            {
                a[k++]=aa;
                if(aa>max)
                max=aa;
            }
        }

        for( i=1; i*max<=x; i++)//求集合的最小公倍数
        {
            for( j=0; j<k; j++)
            if((i*max)%a[j]!=0)
            break;
            if(j==k)
            {
                if((max*i)==x)flog=1;
                break;
            }
        }
        printf("Case #%d: ",tm-t);
        printf("%s\n",flog==1?"Yes":"No");
    }
}