Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CRYPTKEY - VOI 2015 Day 1 - Chìa khóa mã số

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 a1, a2, ..., an. 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ố a1, a2, ..., an là thuộc vào S.

Qui tắc 2. Nếu x у 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 a1, a2, ..., an 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.


Dữ liệu vào: 

 

  • Dòng đầu tiên chứa số nguyên dương T (T ≤ 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 a1, a2, ..., an (ai ≤ 1012);
  • Dòng thứ ba chứa số nguyên dương k (k ≤ 1012).
  • 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.
  • Có 50% số test ứng với 50% số điểm của bài có n ≤ 10.
  • Có 50% số test còn lại ứng với 50% số điểm của bài có n ≤ 50000.

 

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

Dữ liệu ra:

Ràng buộc:

Example

Input:

2
45 75
15
2
45 75
9

Output:

YES
NO

Được gửi lên bởi:VOJ Team
Ngày:2015-01-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI15 day 1

hide comments
2017-08-15 10:03:45
code và lời giải chi tiết:
https://vietcodes.github.io/code/43/
2017-01-14 13:16:18
Code pascal: http://shink.in/4ibJ2
2016-02-09 15:16:01 xin đừng quên tôi
tham khảo tại: http://yeulaptrinh.pw/19/spoj-cryptkey/
2016-01-01 04:47:50 Prismatic
thử 2 test này nha
2
2 4
1

2
2 3
1
:3 cái YES cái NO á
2015-12-16 02:16:08 never give up !!
1
2
2 1
1
ai 98 thử test này nha :v
2015-12-03 13:30:20
30đ :)))))))))
2015-11-16 17:16:57 xin đừng quên tôi
98 là WA nhé
2015-11-05 08:08:37 avfsalkjfas
Các bạn được 98 điểm chú ý tràn số đó nha "=.="


Last edit: 2015-11-06 03:41:52
2015-10-23 11:34:28 VOJ Team
test update anh rejudge
chia buồn cùng các bạn mất ac :v :v
2015-08-15 19:13:19 trọng
Các bạn có thể cho mình ý tưởng giải bài này được không? thanks mọi người!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.