O(n)也要150ms啊...

cutedog,

你难道不能说得明白些???

这个题O(N)的算法就可以了吧.

var
    count:array[0..100000] of longint;
    i,n,k,temp,tot,temp2:longint;
begin
    readln(n,k);    
    fillchar(count,sizeof(count),0);
    temp2:=0;count[0]:=1;
    for i:=1 to n do
        begin
            readln(temp);
            temp2:=(temp2+temp) mod k;
            inc(count[temp2]);
        end;
    tot:=0;
    for i:=0 to k-1 do
        if count[i]<>0 then
                begin
                    inc(tot,(count[i]*(count[i]-1)) shr 1);
                    tot:=tot mod 1234567;
                end;
   **writeln(tot);**
end.

var
    count:array[0..100000] of longint;
    i,n,k,temp,tot,temp2:longint;
begin
    readln(n,k);    
    fillchar(count,sizeof(count),0);
    temp2:=0;count[0]:=1;
    for i:=1 to n do
        begin
            readln(temp);
            temp2:=(temp2+temp) mod k;
            inc(count[temp2]);
        end;
    tot:=0;
    for i:=0 to k-1 do
        if count[i]<>0 then
                begin
                    inc(tot,(count[i]*(count[i]-1)) shr 1);
                    tot:=tot mod 1234567;
                end;
    writeln(tot);
end.