Cho một dãy số gồm N số nguyên và một số nguyên dương k. Hãy tìm một dãy con dài nhất liên tiếp nhau sao cho tổng chia hết cho k.
Dữ liệu vào: từ file DAYSO.INP có dạng:
- Dòng đầu tiên là hai số N và k (N<=500000; k<=10000);
- Các dòng tiếp theo là N số nguyên của dãy (các số kiểu Longint), mỗi số trên một dòng.
Kết quả: ra file DAYSO.OUT gồm một dòng duy nhất chứa hai số m và s, trong đó m là độ dài lớn nhất tìm được và s là vị trí bắt đầu của dãy đó.
const fi = 'CHIAHETK.INP';
fo = 'CHIAHETK.OUT';
MAXN = 10000;
MAXW = 1000;
oo = MAXINT div 2;
var f: text; n: integer;
k: integer;
a: array[1..MAXN] of integer;
L: array[0..MAXN, 0..MAXW] of integer;
procedure Nhap;
var i: integer;
begin
assign(f, fi); reset(f);
readln(f, n, k);
for i:= 1 to n do
read(f, a[i]);
close(f);
end;
function max(a, b: integer): integer;
begin
if a > b then exit(a)
else exit(b);
end;
function dongduduong(s: integer): integer;
begin
s:= s mod k; // -(k-1)..0..k-1
if s >= 0 then exit(s)
else exit(s + k);
end;
procedure QHD;
var i, j: integer;
begin
// Goi L[i, v] la do dai cua day con dai nhat co tong chia k du v
for j:= 0 to k-1 do
if j = dongduduong(a[1]) then L[1, j]:= 1
else L[1, j]:= -oo;
for i:= 2 to n do
for j:= 0 to k-1 do
L[i, j]:= max(1 + L[i-1, dongduduong(j-a[i])], L[i-1, j]);
end;
procedure TruyVet(i, j: integer);
begin
if i = 0 then exit;
if L[i, j] = 1 + L[i-1, dongduduong(j-a[i])] then
// Chon do vat thu i
begin
TruyVet(i-1, dongduduong(j-a[i]));
write(f, a[i], ' ');
end
else
// Khong chon do vat thu i
TruyVet(i-1, j);
end;
procedure InKQ;
var i, j:integer;
begin
assign(f, fo); rewrite(f);
writeln(f, L[n, 0]);
TruyVet(n, 0);
close(f);
end;
BEGIN
Nhap;
QHD;
InKQ;
END.
program SEQ11;
var n,k,s,dem,max:qword;
a:array[1..10000000] of qword;
i,j:longint;
begin
readln(n,k);
for i := 1 to n do read(a[i]);
max := 0; i := 1;
repeat
s := 0;
dem := 0;
for j := i to n do
begin
s := s+a[j];
inc(dem);
if s mod k = 0 then
if max < dem then max := dem;
end;
inc(i);
until i = n;
write(max);
end.
