1413. Lattice Points Under a Straight Line

For each query print the sum of floor((a*i + b) / m) for i from 0 to n - 1.

You are guaranteed 0 <= a < m and 0 <= b < m, so every term is at most i, and every quantity in the problem is non-negative.

n = 5, m = 3, a = 2, b = 1 i = 0: floor(1/3) = 0 i = 1: floor(3/3) = 1 i = 2: floor(5/3) = 1 i = 3: floor(7/3) = 2 i = 4: floor(9/3) = 3 total 7

Geometrically the sum counts the lattice points (i, y) with 1 <= y <= (a*i + b)/m and 0 <= i < n, that is the integer points strictly under the line y = (a*x + b)/m over that strip. Both readings are useful and the second is what makes the fast method visible.

## What most people try first

Loop i from 0 to n - 1. With n at 10^9 and 100 queries that is 10^11 divisions. There is no closed form in general either: the answer depends on a and m in a way that genuinely involves their continued fraction.

## A Euclidean reduction

Two reductions shrink the problem, and the third step is the interesting one.

Strip off the whole part of the slope. If a >= m, then floor((a*i + b)/m) = i * (a/m) + floor(((a mod m)*i + b)/m), and the first part sums to (a/m) * (n-1)*n/2 in closed form. Same for b. After this, a < m and b < m.

Swap the axes. Now count the same lattice points by row instead of by column. The highest row reached is y_max = floor((a*(n-1) + b)/m), and the number of points in row y is the number of i < n with a*i + b >= y*m. Counting that way turns the problem into another instance of the same sum with n and m replaced by y_max and a. Since a < m, the parameters shrink exactly as they do in the Euclidean algorithm, so the recursion terminates in O(log m) steps:

loop: if a >= m: ans += (n-1)*n/2 * (a/m); a %= m if b >= m: ans += n * (b/m); b %= m y = a*n + b if y < m: return ans n = y/m; b = y%m; swap(a, m)

## Why it is correct

The first two reductions are algebraic identities: floor((x + c*m)/m) = floor(x/m) + c for any integer c, applied with c = i * (a/m) and then c = b/m. Nothing is approximated.

The swap is the geometric step. The set of lattice points under the line is counted once by columns, which is the original sum, and once by rows. Counting by rows asks, for each y from 1 up, how many columns reach at least that high, and that count is itself a floor of a linear function of y. Rewriting it gives the same shape of sum with the roles of the slope's numerator and denominator exchanged. Because a < m holds when the swap happens, the pair (a, m) strictly decreases in the Euclidean sense, which is why the loop cannot run forever.

## The boundary that breaks a careless implementation

The loop must terminate on y < m, where y = a*n + b is the highest numerator reached. If that test is placed before the two strip-off steps, a case with a >= m can be returned early with the whole part unaccounted for. And n = 1 must give floor(b/m), which is 0 under the stated guarantee, so a (n-1)*n/2 written as n*n/2 would be silently wrong by a whole term.

## Overflow

a * n reaches about 10^18, and the stripped-off term (n-1)*n/2 * (a/m) reaches a similar size, so both need a signed 64-bit integer, whose limit is 9223372036854775807. A signed 32-bit integer stops at 2147483647 and a 32-bit build answers 0 where the truth is 499999999500000000. The answer is bounded by (n-1)*n/2, about 5 * 10^17, because the guarantee a < m makes every term at most i. That bound is why no modulus is needed, and it is checked rather than hoped: the oracle re-runs the reduction with an assertion on every intermediate. In JavaScript all of these pass 2^53, so BigInt is required.

## Cost

O(log m) per query.

Constraints - `1 ≤ q ≤ 1000` - `1 ≤ n ≤ 1000000000` - `1 ≤ m ≤ 1000000000` - `0 ≤ a < m` - `0 ≤ b < m`