The hardest gcd problem
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.You are given a sequence $A_1, A_2, \dots, A_N$ of positive integers and an integer $K$. You are allowed to perform the following operation any number of times (including zero): - choose an index $j$ between $1$ and $N$ inclusive - choose a positive divisor $d$ of $A_j$ such that $d \le K$ - divide $A_j$ by $d$ Determine if it is possible to modify the sequence $A$ in such a way that it would satisfy the following condition: there is no positive integer strictly greater than $1$ which divides every element of $A$. (In other words, the greatest common divisor of all elements of $A$ should be $1$.) ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $K$. - The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$. ### Output For each test case, print a single line containing the string `"YES"` if it is possible to make the GCD of all elements of $A$ equal to $1$ or `"NO"` if it is impossible. ### Constraints - $1 \le T \le 10$ - $1 \le N \le 10^5$ - $1 \le A_i \le 10^9$ for each valid $i$ - $1 \le K \le 10^9$ ### Subtasks **Subtask #1 (30 points):** - $1 \le N, K \le 100$ - $1 \le A_i \le 100$ for each valid $i$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 2 3 6 10 15 30 3 4 5 10 20 ``` ### Example Output ``` YES NO ```
|Tags||altruist_, basic-math, easy, ltime59|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.