連結:戳這裡
D. Remainders Game time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output 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 numbers c1, 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.
Examples
input
4 5
2 3 5 12
output
Yes
input
2 7
2 3
output
No
Note
In the first sample, Arya can understand because 5 is one of the ancient numbers.
In the second sample, Arya can't be sure what is. For example 1 and 7 have the same remainders after dividing by 2 and 3, but they differ in remainders after dividing by 7.
題意:
給定n和k,要求去猜x%k的值,其中n個數ci表示知道了所有的x%ci的值
問能不能知道x%k的值
思路:
根據中國剩餘定理若要求出x%k的值,k=m1*m2*m3*...mn
其中mi互素,且k必須分解成k=p1^a1*p2^a2*...*pn^an (其中pi為素數)
那麼我們隻需要判斷所有的ci的乘積能不能分解出一個數Y使得Y==k,由于數太大會爆ll
是以對于目前ci,我們都取出目前所有ci的LCM,再跟k取GCD
那麼這個GCD肯定是k中的一部分,最後判斷所取出來的GCD能否拼成k
代碼:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
ll n,K;
ll c[1000100];
ll GCD(ll a,ll b){
return b==0 ? a : GCD(b,a%b);
}
ll LCM(ll a,ll b){
ll gcd=GCD(a,b);
return a*b/gcd;
}
int main(){
scanf("%I64d%I64d",&n,&K);
for(int i=1;i<=n;i++) scanf("%I64d",&c[i]);
ll lcm=1;
for(int i=1;i<=n;i++){
lcm=LCM(lcm,c[i]);
lcm=GCD(lcm,K);
if(lcm==K) {
printf("Yes\n");
return 0;
}
}
printf("No\n");
return 0;
}