1409. How Many Multiples Lie in the Range
For each query count the integers x with L <= x <= R that are multiples
of k. Both L and R may be negative. k is positive. Zero counts as a
multiple of every k.
L = 1, R = 10, k = 3 -> 3 3, 6, 9
L = -10, R = -1, k = 3 -> 3 -9, -6, -3
L = -10, R = 10, k = 3 -> 7 -9 -6 -3 0 3 6 9
L = 4, R = 5, k = 3 -> 0
## What most people try first
Loop from L to R and test divisibility. The range reaches 2 * 10^18
integers wide, so that is not a slow solution, it is an impossible one. The
second attempt is R / k - L / k, which is close but wrong twice over: it
excludes L itself when L is a multiple, and in C, C++, Java and JavaScript
the division truncates toward zero rather than flooring, which breaks every
negative case.
## Count the prefix, twice
Let f(x) be the number of multiples of k in [0, x] for x >= 0, extended
to negative x by counting with a sign. The clean statement is: the number of
multiples of k at or below x is exactly floor(x / k) plus one for the
multiple 0, and the one cancels when two such counts are subtracted. So
answer = floor(R / k) - floor((L - 1) / k)
The L - 1 is what includes L itself: the second term counts the multiples
strictly below L.
## Why it is correct
floor(x / k) is the number of positive multiples of k at or below x when
x >= 0, and minus the number of multiples strictly above x and at or below
0 when x < 0. In both cases the function x -> floor(x/k) increases by
exactly 1 each time x passes a multiple of k, and by 0 otherwise. So the
difference floor(R/k) - floor((L-1)/k) counts precisely the multiples in
(L - 1, R], which is [L, R] over the integers. The argument never splits on
the sign of L or R, which is why the code does not either, provided the
division really floors.
## The boundary that breaks a careless implementation
floor is not what / gives in four of the five reference languages.
-10 / 3 truncates to -3 while the floor is -4, so a truncating build reports
2 for the second worked example instead of 3. The correction is the one from
problem 1406: subtract 1 when the division is inexact and the signs differ.
Python's // needs no correction, which is exactly why a solution tested only
in Python looks fine and then fails in the other four.
## Overflow
L and R reach 10^18 in magnitude, so they need 64 bits; a 32-bit build
answers 1321730049 where the truth is 2000000000000000001. The answer
itself reaches 2 * 10^18 + 1 when k is 1, which still fits a signed 64-bit
integer, whose limit is 9223372036854775807, so no modulus is needed. L - 1
reaches -10^18 - 1, also comfortably inside 64 bits. In JavaScript every one
of these is past 2^53, so BigInt is required for the inputs and for the
result.
## Cost
O(1) per query.
Constraints - `1 ≤ q ≤ 1000` - `-1000000000000000000 ≤ L ≤ R ≤ 1000000000000000000` - `1 ≤ k ≤ 1000000000000000000`
Input
The first line contains q.
Each of the next q lines contains L, R and k, with L <= R.
Output
For each query print the count, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.