首页 > 代码库 > XTU1199:Number Game
XTU1199:Number Game
题目描写叙述
给你一个有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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。