VOI 15 Bài 2 - Chìa khóa mã số

View as PDF

Submit solution

Points: 1.21 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI15 day 1
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Duy vừa xây dựng hệ thống mã hóa bảo mật dữ liệu cho cơ quan dựa trên cơ sở hệ mã hóa với khóa công khai. Biết rằng, trong hệ thống này khóa được sử dụng để mã hóa là một số nguyên dương thuộc tập ~S~ gồm các khóa mã hóa được xây dựng dựa trên tập gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Theo định nghĩa, tập ~S~ là tập chỉ gồm các số được xác định theo ~2~ qui tắc sau đây:

Qui tắc ~1~: Các số ~a_1, a_2, \dots, a_n~ là thuộc vào ~S~.

Qui tắc ~2~: Nếu ~x~ và y thuộc tập ~S~, thì cả ước số chung lớn nhất lẫn bội số chung nhỏ nhất của chúng cũng đều thuộc tập ~S~.

Vấn đề đặt ra cho Duy bây giờ là: Kiểm tra xem một số nguyên dương ~k~ có thuộc vào tập các khóa ~S~ hay không?

Yêu cầu: Cho ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ và một số nguyên dương, hãy kiểm tra xem ~k~ có thuộc vào tập các khóa xây dựng theo các qui tắc đã nêu hay không.

Input

  • Dòng đầu tiên chứa số nguyên dương ~T~ (~T \leq 5~) là số lượng bộ dữ liệu;

  • Mỗi nhóm trong số ~T~ nhóm dòng tiếp theo mô tả một bộ dữ liệu gồm ~3~ dòng:

    • Dòng thứ nhất chứa số nguyên dương ~n~;
    • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \leq 10^{12}~);
    • Dòng thứ ba chứa số nguyên dương ~k~ (~k \leq 10^{12}~).

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

  • Ghi ra ~T~ dòng, mỗi dòng ghi câu trả lời cho một bộ dữ liệu tương ứng trong file dữ liệu vào: ghi 'YES' nếu như ~k~ thuộc vào tập khóa và ghi 'NO' nếu như trái lại.

Giới hạn

  • Có 50% số test ứng với 50% số điểm của bài có ~n \leq 10~.
  • Có 50% số test còn lại ứng với 50% số điểm của bài có ~n \leq 50000~.

Sample Input

2
2
45 75
15
2
45 75
9

Sample Output

YES
NO

Comments

Please read the guidelines before commenting.


There are no comments at the moment.