1368. The Remainder That Is Never Negative
For each query a m, print the remainder of a divided by m as the least
non-negative value, so the answer always lies in 0 to m-1.
7 3 -> 1
-7 3 -> 2 because -7 = -3 * 3 + 2
0 3 -> 0
## What most people try first
Print a % m. On the first and third lines that is right. On the second it
prints -1 in C, C++, Java and JavaScript, and 2 in Python, and only one of
those is the answer this problem wants.
The difference is not a bug in any of them. It is a choice about which way division rounds, and the five languages did not all make the same choice:
language -7 / 3 -7 % 3
C, C++ -2 -1 truncates toward zero
Java -2 -1 truncates toward zero
JavaScript n/a -1 truncates toward zero
Python -3 2 floors toward negative infinity
A language that truncates gives a remainder with the sign of a. A language
that floors gives a remainder with the sign of m. Since m is positive here,
flooring is exactly what the question asks for.
## The fix, and why one addition is enough
r = a % m
if r < 0: r = r + m
The truncating remainder always satisfies -m < r < m, because its absolute
value is strictly less than |m| by the definition of remainder. So when it is
negative, adding m once lands it in 0 to m-1 and never overshoots. A
second addition could never be needed, and ((a % m) + m) % m is the same fix
written to work even when m might be negative.
## Why not just take the absolute value
abs(-7) % 3 is 1, not 2. Negating changes which multiple of m you are
measuring from, and -7 sits 2 above -9 while 7 sits 1 above 6. The two
are different questions whenever a is not a multiple of m.
## Overflow
a runs to 10^18 in magnitude, which needs a signed 64-bit integer: 32 bits
stops at 2147483647. After the remainder, every value is below 10^9 and small
again. In JavaScript 10^18 is past the 2^53 a Number represents exactly,
so the input cannot even be parsed correctly without BigInt.
## Cost
O(1) per query, O(q) in total.
Constraints - `1 ≤ q ≤ 200000` - `-1000000000000000000 ≤ a ≤ 1000000000000000000` - `2 ≤ m ≤ 1000000000`
Input
The first line contains the integer q, the number of queries.
Each of the next q lines contains two integers a and m.
Output
Print q lines. Line i holds the remainder of query i as the least non-negative residue, in the range 0 to m-1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.