Biến đổi dãy số
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử và số nguyên ~X~. Ta định nghĩa dãy con ~S~ của dãy ~A~ là dãy mà không có tổng 2 phần tử bất kì nào trong dãy chia hết cho ~X~ được tạo ra bằng cách giữ nguyên hoặc xóa đi bớt 1 số phần tử của dãy ~A~.
Yêu cầu: Tìm độ dài lớn nhất của dãy con ~S~ sau khi biến đổi dãy ~A~
Input:
Dòng đầu tiên chứa 2 số nguyên ~N~ và ~X~ (~N, X \le 9.10^5~)
Dòng tiếp chứa dãy ~A~ gồm ~N~ phần tử (~A_i \le 10^{18}~)
Output:
- Gồm một dòng duy nhất là yêu cầu của bài toán
Example
Input:
10 3
842 713 908 552 346 84 160 604 443 860
Output:
6
Dữ liệu:
- Subtask 1 (25% số điểm): ~N, X \le 10^2, Ai \le 10^5~.
- Subtask 2 (20% số điểm): ~N, X \le 10^3, Ai \le 10^9~.
- Subtask 3 (20% số điểm): ~N, X \le 4.10^4, Ai \le 10^{12}~.
- Subtask 4 (20% số điểm): ~N, X \le 4.10^5, Ai \le 10^{15}~.
- Subtask 5 (15% số điểm): Không có ràng buộc gì thêm.
Bình luận
anh Shinoz beo béo
:)
bài này có nhiều thk nghĩ là LIS hoặc dùng 2 vòng for chạy lồng nhau thì có cái nịt nhé:DDDDDDDDDDDDDDD
có căn ms nghĩ là LIS, trâu vẫn ăn test nma bị TLE
:0
Test đang yếu khi nầu rảnh t sinh lại:D, có thể sẽ tăng số test + tăng dữ liệu (btw bài tương đối dễ nên t sẽ k viết sol nhé, thg nầu rảnh thì cứ việc viết dùm t)
vl ác:)))
ác v :<<
.
meow