D - Remainders Game
Description
Today Pari and Arya are playing a game called Remainders.
Pari chooses two positive integer x and k, and tells Arya k but not x.
Arya have to find the value . There are n ancient numbersc1,
c2, ..., cn and Pari has to tell Arya if Arya wants. Given k and
the ancient values, tell us if Arya has a winning strategy independent
of value of x or not. Formally, is it true that Arya can understand the
value for any positive integer x?
Note, that means the remainder of x after dividing it by y.
Input
The first line of the input contains two integers n and k
(1 ≤ n, k ≤ 1 000 000) — the number of ancient integers and value
k that is chosen by Pari.The second line contains n integers c1, c2,
..., cn (1 ≤ ci ≤ 1 000 000).
Output
Print "Yes" (without quotes) if Arya has a winning strategy independent
of value of x, or "No" (without quotes) otherwise.
Sample Input
4 5
2 3 5 12
Yes
2 7
2 3
No 题意：给定n，k,和n个ci。你可以知道x%ci,问是否能确定x%k.
分析：根据中国剩余定理问题就相当于要确定 C 数组整体的最小公倍数 lcm(c)
是否是 K 的倍数，如果是，则能确定输出 yes，否则输出 no.
#include <iostream>
#include<cstdio>
#define LL long long
using namespace std;
int a;
int gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
int main()
{
LL n,k,lcm=;
scanf("%lld%lld", &n, &k);
for(int i=;i<n;i++)
{
scanf("%lld", &a);
lcm = lcm / gcd(lcm, a) * a % k;
}
if(lcm%k==) printf("Yes\n");
else printf("No\n");
return ;
}