Tập GCD

Xem PDF




Tác giả:
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 300 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một hôm, Đức nghĩ ra một cách xây dựng một tập hợp số nguyên dương, gọi là \(S\), rồi đố Hân xác định xem một số nguyên dương \(K\) bất kỳ có thuộc tập \(S\) hay không. Biết rằng tập \(S\) của Đức chỉ gồm các số xác định theo hai quy tắc:

  • Quy tắc 1: Các số \(a_1\), \(a_2\),..., \(a_n\) thuộc \(S\).
  • Quy tắc 2: Nếu \(a\)\(b\) thuộc \(S\) thì ước số chung lớn nhất của \(a\)\(b\) cũng thuộc \(S\).
    Vì số phần tử của tập S có thể rất lớn nên Hân đành phải nhờ bạn lập trình tính toán giúp để trả lời câu hỏi của Đức. Bạn hãy giúp Hân nhé!

Input

  • Dòng đầu chứa số nguyên dương \(T\) thể hiện số câu hỏi.
  • Mỗi nhóm trong \(T\) nhóm dòng tiếp theo mô tả một câu hỏi, gồm:
  • Dòng đầu chứa hai số nguyên dương \(n\)\(K\).
  • Dòng tiếp theo chứa \(n\) số nguyên dương phân biệt \(a_1\), \(a_2\),..., \(a_n\).

Output

  • Gồm \(T\) dòng, mỗi dòng in ra YES nếu \(K\) nằm trong tập \(S\) tương ứng, hoặc in ra NO trong trường hợp ngược lại.

Constraints

  • \(T\leq 5\)
  • \(n\leq 20000, a_i\leq 10^{12}, K\leq 10^{12}\)

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n\leq 20, a_i\leq 10^6, K\leq 10^6\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n\leq 20000, a_i\leq 10^6, K\leq 10^6\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input
2
5 4
24 2 60 6 40
2 3
9 10 
Output
YES
NO

Bình luận