题目描写叙述
给你一个有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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll __int64
ll a[100005],p[100005],len; ll gcd(ll a,ll b)
{
if(b)
return gcd(b,a%b);
else return a; } int main()
{
ll t,n,x,i,j,r,cas = 1,sum;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&x);
sum = 1;
for(i = 0; i<n; i++)
{
scanf("%I64d",&a[i]);
sum = (sum*a[i])%x;
}
printf("Case #%d: ",cas++);
if(sum%x)
printf("No\n");
else
{
int flag = 0;
len = 0;
for(i = 0; i<n; i++)
{
if(x%a[i] == 0)
p[len++] = a[i];
}
ll ans = 1;
for(i = 0; i<len; i++)
{
if(ans<p[i])
ans = (ans*p[i])/gcd(p[i],ans);
else
ans = (ans*p[i])/gcd(ans,p[i]);
if(ans==x)
{
flag = 1;
break;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
} return 0;
}