Mã bài:
thtla_22c_2
Điểm:
1,5 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dữ liệu vào:
GCD.INP
Dữ liệu ra:
GCD.OUT
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Cho tập ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ và số nguyên dương ~D~.
Yêu cầu: Tìm một tập con của ~A~ sao cho ước chung lớn nhất của các phần tử trong tập con bằng ~D~.
Lưu ý: Gọi ước chung lớn nhất của ~a~ và ~b~ là ƯCLN~(a, b)~. Ước chung lớn nhất của ba số được tính bằng công thức ƯCLN~(a, b, c) = ~ ƯCLN~(~ƯCLN~(a, b), c)~.
Dữ liệu vào:
Từ tập tin văn bản GCD.INP
gồm:
- Dòng đầu tiên chứa hai số ~N, D~ ~(1 \le N \le 1000, 1 \le D \le 10^9)~.
- Dòng thứ hai gồm ~N~ số, số thứ ~i~ là ~A_i~ ~(1 \le A_i \le 10^9)~.
Kết quả ra
Xuất ra tập tin văn bản GCD.OUT
:
- Dòng thứ nhất chứa số lượng phần tử
- Dòng thứ hai chứa các phần tử của tập con tìm được, các số trên cùng một dòng cách nhau ít nhất một dấu cách.
Nếu có nhiều tập con thỏa mãn yêu cầu thì xuất ra một tập con bất kì. Nếu không tìm được tập con thỏa mãn yêu cầu thì xuất ra màn hình -1
.
Ví dụ 1
GCD.INP
4 7
14 35 6 21
GCD.OUT
3
14 35 21
Ví dụ 2
GCD.INP
4 3
5 2 10 7
GCD.OUT
-1
Bình luận