1412. Add Up the Multiples in the Range

For each query print the sum of every multiple of k in [L, R]. Both L and R may be negative. k is positive. If the range contains no multiple, print 0.

L = 1, R = 10, k = 3 -> 18 3 + 6 + 9 L = -10, R = -1, k = 3 -> -18 -9 + -6 + -3 L = -10, R = 10, k = 3 -> 0 the two cancel, and 0 adds nothing L = 4, R = 5, k = 3 -> 0 no multiple in range

## What most people try first

Loop over the range. It reaches 2 * 10^9 integers wide, which is already too slow at 1000 queries, and looping over L/k to R/k instead is the same length. The structure to use is that the multiples form an arithmetic progression.

## Count, then one closed form

The multiples of k in [L, R] are consecutive terms of a progression with common difference k. Problem 1409 gives the count, and the first and last terms come from the same two divisions:

count = floor(R/k) - floor((L-1)/k) first = k * ceil(L/k) last = k * floor(R/k) sum = count * (first + last) / 2

## Why it is correct

The sum of an arithmetic progression is the number of terms times the average of the first and last, which is the usual pairing argument: write the sum forwards and backwards, add them termwise, and every column is first + last. That argument never assumes the terms are positive, so it holds unchanged for a range below zero or straddling it.

first is the smallest multiple of k at or above L, which is k * ceil(L/k), and last is the largest at or below R, which is k * floor(R/k). Both of those need the rounding conventions of problems 1406 and 1407, not a plain /, since L and R may be negative.

## The boundary that breaks a careless implementation

count * (first + last) is always even, so the halving is exact and does not need a rounding rule of its own. The reason: the count and the number of terms are the same thing, and for an arithmetic progression either the count is even, or the count is odd and then first + last is twice the middle term. So dividing by 2 after multiplying is exact, while dividing (first + last) by 2 first would truncate when the count is even and first + last is odd.

The empty range is the other edge. When no multiple lies in [L, R] the count comes out 0 or negative and first is then larger than last, so the formula would produce a nonzero number. The references test the count first and print 0, which the statement pins.

## Overflow

|L| and |R| reach 10^9, so count reaches about 2 * 10^9. Be precise about that figure: 2 * 10^9 does fit a signed 32-bit integer, whose limit is 2147483647. What does not fit is the product: count * (first + last) reaches about 4 * 10^18, which needs a signed 64-bit integer, whose limit is 9223372036854775807, and the answer itself reaches about 5 * 10^17. A 32-bit build answers -243309312 where the truth is 500000000500000000. In JavaScript both figures are past 2^53, so BigInt is required.

## Cost

O(1) per query.

Constraints - `1 ≤ q ≤ 1000` - `-1000000000 ≤ L ≤ R ≤ 1000000000` - `1 ≤ k ≤ 1000000000`