THẺ THÔNG MINHTẬP ĐOÀN SMART IT QUYẾT ĐỊNH ỨNG DỤNG THẺ THÔNG M...
Tập đoàn Smart IT quyết định ứng dụng thẻ thông minh trong
việc quản lý an ninh. Mỗi nhân viên của Smart IT được cấp
một thẻ thông minh riêng, trong thẻ chứa một dãy số bí mật
gồm m số nguyên dương {k
1
, k
2
, … k
m
}.
Trong nhà điều hành của SmartIT có n căn phòng được đánh
số từ 1 đến n. Ở cửa vào của căn phòng thứ i (1 ≤ i ≤ n) có một
đầu đọc thẻ. Khi cần mở cửa phòng, người nhân viên sẽ đưa
thẻ vào đầu đọc thẻ. Nếu thẻ phù hợp với phòng thì cửa sẽ mở.
Trong đầu đọc thẻ ở phòng thứ i có lưu một dãy số nguyên
dương {x
i1
, x
i2
, …, x
im
}. Thẻ phù hợp với phòng thứ i nếu
tích k
1
× k
2
× … ×
k
m
là bội số của tích x
i1
× x
i2
× … ×
x
im
.
Yêu cầu: Cho biết dãy số bí mật trong thẻ thông minh và các dãy số trong đầu đọc thẻ của
n căn phòng. Hãy cho biết thẻ thông minh này có thể dùng để mở được bao nhiêu phòng.
Dữ liệu: Vào từ file văn bản SCARD.INP với cấu trúc như sau:
•
Dòng đầu tiên chứa hai số nguyên dương m và n (với 1 ≤ m ≤ 100 và 1 ≤ n ≤ 5),
•
Dòng thứ hai chứa m số nguyên dương k
1
, k
2
, …, k
m
là dãy số bí mật trên thẻ. Mỗi
số có giá trị không quá 10
9
,
•
Dòng thứ i trong số n dòng tiếp theo (1 ≤ i ≤ n), mỗi dòng gồm m số nguyên dương
x
i1
, x
i2
,…, x
im
là dãy số trong đầu đọc thẻ tại phòng i. Mỗi số có giá trị không quá
10
9
.
Các số trên cùng một dòng được ghi cách nhau bởi 1 khoảng trắng.
Kết quả: Đưa ra file văn bản SCARD.OUT với cấu trúc như sau:
•
Dòng đầu tiên chứa một số nguyên C là số lượng những phòng có thể mở cửa được.
•
Dòng thứ hai chứa C số nguyên là số thứ tự (theo thứ tự tăng dần) của các phòng
mà bạn có thể mở cửa được.
Ví dụ:
SCARD.INP
SCARD.OUT
2
3 4
7 10 2011
1 3 5
2 2 7
7 2 5
14 1 2011