Problem Type 1)

Lets say I have an array A[x1,x2,x3,...xN] of size N.

for N = 4 , A = {x1,x2,x3,x4}. [1 based index]

Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is divisible by K.

For example, N = 4

A = { 3,2,5,7} and K = 5.

Now , For this case the answer is 3. as, ( 1,2 ) [cum_sum = 5 ,divisible by K(5)], (3,3) [cum_sum = 5 ,divisible by K(5)] , (1,3) [ cum_sum = 10 ,divisible by K(5)] are such tuples.

I can do this in O(N^2) easily.But how to do this in O(N) or O(N*log(N)) ?

Please give me some problem links based on this (or similar) idea/trick from CodeForces.