1382. Which Totals Can Be Reached

Two step sizes a and b are given, and you may take any whole number of each step, forwards or backwards. For each query count the integers v in the range L to R inclusive that can be written as:

v = a * x + b * y with x and y any integers, possibly negative

a = 4, b = 6, L = 1, R = 20 -> 10 the even numbers 2,4,...,20 a = 4, b = 6, L = -20, R = -1 -> 10 the even numbers -20,...,-2 a = 4, b = 6, L = -5, R = 5 -> 6 -4,-2,0,2,4 and ... see below

## What is reachable

Every combination a*x + b*y is a multiple of g = gcd(a, b), and by Bezout's identity (problem 1379) g itself is reachable, so every multiple of g is reachable by scaling that combination. So the reachable set is exactly the multiples of g, and the question becomes: how many multiples of g lie in L to R?

Note 0 is always reachable, with x = y = 0, which is why the third example counts six values and not five.

## What most people try first

Count R / g - L / g + 1, or loop over the range. The loop is O(R - L), which is 2 * 10^18 here. The formula is closer but wrong at both ends, and the fix is the point of the problem.

## The count, with the division that actually floors

The number of multiples of g in L .. R is:

floor(R / g) - floor((L - 1) / g)

Count the multiples at or below R, then subtract the multiples at or below L-1. Using L-1 rather than L is what makes the range inclusive at the left end without a separate test for whether L itself is a multiple.

## Floor division is not the division your language gives you

This is where the problem bites, and the convention is stated rather than assumed. Floor division, rounding toward negative infinity, is wanted throughout.

-7 / 2 -7 mod 2 C, C++ -3 -1 truncates toward zero Java -3 -1 truncates toward zero Python -4 1 floors toward negative infinity

So in C, C++, Java and JavaScript the division must be corrected by hand:

q = a / b if a mod b is not 0 and a is negative: q = q - 1

With L = -20, R = -1, g = 2, the truth is floor(-1/2) - floor(-21/2), that is -1 - (-11) = 10. Truncating division gives 0 - (-10) = 10 here by accident, but with L = -7, R = -1, g = 3 the truth is -1 - (-3) = 2 while truncation gives 0 - (-2) = 2 and with L = -1, R = -1 the truth is -1 - (-1) = 0 against truncation's 0 - 0 = 0. The declared tests include the asymmetric cases where the two genuinely differ.

## Overflow

R reaches 10^18 and the count itself reaches 2 * 10^18 + 1, which is past what a signed 32-bit integer holds by nine orders of magnitude and past even a signed 64-bit integer's 9.22 * 10^18 only if the count were squared, which it is not. L - 1 can be -10^18 - 1, still inside 64 bits. In JavaScript a plain Number is exact only below 2^53, so BigInt is required, and BigInt division truncates as well, so it needs the same correction.

## Cost

O(log min(a,b)) per query for the gcd.

Constraints - `1 ≤ q ≤ 1000` - `1 ≤ a ≤ 1000000000` - `1 ≤ b ≤ 1000000000` - `-1000000000000000000 ≤ L ≤ R ≤ 1000000000000000000` - Division must round toward negative infinity, which is not what C, C++, Java or `BigInt` give for a negative numerator.