Thẻ thông minh
Xem PDFTậ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 \times k_2 \times … \times k_m\) là bội số của tích \(x_{i1} \times x_{i2} \times … \times 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.
Input
- Dòng đầu tiên chứa hai số nguyên dương \(m\) và \(n\) (với \(1 ≤ m, n ≤ 100\)),
- 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^{15}\) ,
- 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 \(x_{i1}, x_{i2}, …, x_{im}\). Mỗi số có giá trị không quá \(10^{15}\).
Các số trên cùng một dòng được ghi cách nhau bởi 1 khoảng trắng.
Output
- 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. Các số trên cùng một dòng được ghi cách nhau bởi 1 khoảng trắng
Example
Test 1
Input
3 4
7 10 2011
1 3 5
2 2 7
7 2 5
14 1 2011 Output
2
3 4
Bình luận
số lớn = ez nhé :v
đây là code số lớn bản đầy đủ mình lấy trên codeforce
Thanks anh:) em ăn hên thôi, làm đại mà vẫn ac
hầy em ới, cái thuật em dùng để sàng nt là ntn thía :V, a toàn dùng sàng E nên thấy cái này lạ quá, nhân tiện thì bài ma trận vip giới hạn n tận 1e6 á :V
Cái sàng của em cũng là sàng erathostenes thôi anh, nhưng em cải tiến lên chỉ duyệt các số dạng 6k+-1 thôi, và không duyệt qua các số nhỏ như 2, 3, 5, 7 thì sẽ giảm được rất nhiều thời gian từ việc không cần phải đánh dấu các bội của 2, 3, 5, 7 ạ.
Em xài bitset (nếu là số nguyên tố thì đánh dấu là 0, ngược lại đánh dấu là 1). Lúc đầu em đánh dấu nếu là số nguyên tố thì đánh dấu 1, còn ngược lại thì đánh dấu 0 cơ, nhưng thấy làm vậy thì phải có một vòng lặp duyệt từ 2 đến limit để đánh dấu 1 hết nên khá tốn thời gian.
Đây là sàng của em: https://ideone.com/l6NHun
thanks anh vì cái code bignum và giới hạn bài ma trận vip nhé:)
mơm e nhó hì 😊
anh chơi đểu:) anh xài bignum, còn code của em tận 6 giây hmu hmu
hì hì, a lười sàng nên giải bignum cho nhanh :>, cơ mà e xử lý hay v$