First, we need to find an efficient way of generating the following sequence:

$$\displaystyle A \bmod B + (2A) \bmod B + (3A) \bmod B + \dots + (nA) \bmod B \tag{0}$$

Known formula gives us (where ~[x]~ is the integer part of ~x~ and ~\{x\}~ is the fractional part of ~x~):

$$\displaystyle [x] + \{x\} = x \tag{1a}$$ $$\displaystyle (A \bmod B) / B = \{A/B\} \tag{1b}$$

Combining (0), (1a) and (1b) we have:

$$\displaystyle A \times (1+2+\dots+n) = B \times ([A/B]+[2A/B]+\dots+[nA/B]) + B \times (\{A/B\}+\{2A/B\}+\dots+\{nA/B\}) \tag{2}$$

From (2) we see that we can solve (0) if we can solve:

$$\displaystyle [A/B]+[2A/B]+\dots+[nA/B] \tag{3}$$

Note that (3) can be interpreted geometrically: How many lattice points are in the triangle ~(0,0)~ ~(n,0)~ ~(n, nA/B)~ if we exclude lattice points on the ~x~ axis?

Let us examine the following two cases:

• ~A \ge B~

There exists a nonnegative integer ~k~ and integer ~r~ from ~[0, B-1]~ such that ~A = kB + r~. We use this and (3) to obtain:

$$\displaystyle [(kB+r)/B]+[2(kB+r)/B]+\dots+[n(kB+r)/B] = [r/B]+[2r/B]+\dots+[nr/B]+k \times (1+2+\dots+n)$$

This reduces this case to the following case.

• ~A < B~

Let the rectangle ~(0,0)~ ~(n, nA/B)~ be labeled ~P~. We can easily calculate the number of lattice points in ~P~. We are interested in the number of lattice points beneath its diagonal. This can be calculated by subtracting the number of points above the diagonal from the total number of points. The number of points above the diagonal can be found simpler than the number of points beneath it.

Now, by relabeling axes ~x~ and ~y~, we reduce the second case back to the first case. These reductions 1 → 2 → 1 can only be performed a finite number of times because the sum ~A+B~ decreases each time we solve the first case. By following this we can compute members of (0) in ~\mathcal O(\log n)~. Now we just need to store the array in a fast data structure. It turns out using interval/tournament tree gives the total complexity ~\mathcal O(n \log^2 n)~. Enough to solve the task.