Online algorithms - requests

magzim

I have some algorithmic problem. Imagine we have array ARR filled with n zeros(n = 500000) and two types of requests(number of requests - 500000):

1)recieve 2 numbers X and Y and set ARR[X] = Y (0 <= X <= n, -1000 <= Y <= 1000);

2)recieve 2 numbers X and Y and find sum of elements ARR[k] where k mod X = Y(0 <= X <= n, 0 <= Y <= X);

My limits: time - 2 sec, memory - 256mb;

I tried to calculate the sum using a loop:

for(i = y; i <= n; i += x) {

sum += arr[i];

}

but it`s very slow.

I don't know what else i can try, do you have any ideas ?