2025 THT bảng B - Buổi 22 - GCD

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\) và \(b\) thuộc \(S\) thì ước số chung lớn nhất của \(a\) và \(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\) và \(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

2
5 4
24 2 60 6 40
2 3
9 10 

YES
NO

Khôi có một mảng số tự nhiên \(A\) có \(N\) phần tử. Anh ấy phải tìm ra tất cả các số đặc biệt \(K\).

Biết rằng số đặc biệt \(K\) phải thỏa mãn những điều sau:

1) K>1

2) A[1]%K = A[2]%K = A[3]%K = ... = A[N]%K

Input

• Dòng đầu tiên chứa \(1\) số nguyên dương \(N (2 ≤ N ≤ 10^5)\)
• Gồm \(N\) dòng, dòng \(i\) chứa giá trị của \(A_i (1 ≤ A_i ≤ 10^9)\)
• Các số trong mảng \(A\) khác nhau đôi một
  Dữ liệu Input đảm bảo có ít nhất \(1\) số \(K\) thỏa mãn và nhiều nhất 106106 số \(K\) thỏa mãn

Output

• Tất cả các số đăc biệt K theo thứ tự tăng dần. (Mỗi số trên 1 dòng)

Example

3
38
6
34 

2
4

.