CẤP SỐ CỘNG TRONG TOÁN HỌC, MỘT CẤP SỐ CỘNG LÀ MỘT DÃY SỐ, TRON...

Bài 4. Cấp số cộng Trong toán học, một cấp số cộng là một dãy số, trong đó kể từ số hạng thứ hai, mỗi số hạng đều là tổng của số hạng đứng ngay trước nó với một số không đổi gọi là công sai. Chẳng hạn, dãy số 3, 5, 7, 9, 11 là một cấp số cộng với các phân tử liên tiếp với công sai là 2. Cho dãy số nguyên a

1

, a

2

, …, a

n

. Ta định nghĩa một dãy con là dãy nhận được từ dãy trên bằng cách bỏ đi một số phần tử (có thể bằng 0) và giữ nguyên thứ tự các phần tử còn lại.

-2-

Yêu cầu: Cho dãy n số nguyên a

1

, a

2

, …, a

n

và giá trị công sai d cho trước. Hãy tìm dãy con dài nhất của dãy trên lập thành một cấp số cộng với công sai d (các phần tử có thể ở vị trí bất kì trong dãy). Để đơn giản ta chỉ cần tìm số lượng phần tử của dãy con này.Dữ liệu: Vào từ file văn bản BAI4.INP Dòng đầu tiên ghi số nguyên dương n (n ≤ 10

⁵

) và giá trị công sai d (0≤d≤100) Dòng thứ hai ghi n số nguyên a

1

, a

2

, …, a

n

(1≤a

i

≤10

⁶

). Hai số liên tiếp ghi cách nhau ít nhất một dấu cáchKết quả: Ghi ra file văn bản BAI4.OUT một số nguyên duy nhất là kết quả tìm được. Ví dụ:

BAI4.INP

BAI4.OUT

10 3

6

1 2 4 7 8 10 8 12 13 16

Giải thích: Dãy con dài nhất của dãy 10 phần tử trên thành lập cấp số cộng công sai 3 gồm 6

phần tử là: 1, 4, 7, 10, 13, 16

Ghi chú: Kết quả được chấm qua 6 test, mỗi test đúng được 0,25 điểm, trong đó:



2 test có n≤500



2 test có n≤5000



2 test có n≤10

⁵