#425. DPSEQMODK – Dãy con có tổng chia hết cho K

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy gồm N số nguyên dương a_1, a_2, ..., a_n và số nguyên dương K . Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho K .

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương N K cách nhau bởi một khoảng trắng;
  • Dòng thứ hai ghi N số a_1, a_2, ..., a_n , mỗi số cách nhau bởi một khoảng trắng.

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số phần tử của dãy dài nhất tìm được.

Ví dụ:

Dữ liệu vào:
10 3
3 2 5 7 9 6 12 7 11 15
Dữ liệu ra:
9
Giải thích:
  • Dãy dài nhất có 9 phần tử là 3, 5, 7, 9, 6, 12, 7, 11, 15

Giới hạn:

  • 1 ≤ N ≤ 1000; 1 ≤ K ≤ 100; |a_i|≤ 10^9