1407. Round the Division Up, Either Sign
For each query print ceil(a / b), the smallest integer that is at or above
the true quotient. Either operand may be negative.
a = 7, b = 2 -> 4 the true quotient is 3.5
a = -7, b = 2 -> -3 the true quotient is -3.5
a = 7, b = -2 -> -3
a = -7, b = -2 -> 4
## What most people try first
(a + b - 1) / b. It is the standard trick, it is correct for positive
operands, and it is wrong the moment a sign is negative. With a = -7 and
b = 2 it computes (-7 + 1) / 2 = -6 / 2 = -3, which happens to be right;
but with a = -8 and b = 3 it computes (-8 + 2) / 3 = -2, while the true
ceiling of -8/3 = -2.67 is -2 as well. The trick survives those and then
fails on a = 7, b = -2, where it computes (7 - 3) / (-2) = -2 against a
true answer of -3. It also overflows: a + b with both near 10^18 is near
2 * 10^18, and with both near the 64-bit limit it wraps.
The other common attempt is (long long) ceil((double) a / b). A double
has 53 bits of mantissa while |a| reaches 10^18, so the division is
already inexact before ceil runs, and the result can be off by one in
either direction.
## One identity, no case analysis
ceil(a / b) = -floor(-a / b)
Negating the numerator reflects the true quotient about zero, which turns rounding down into rounding up, and negating again puts it back. So a correct floor division is the only primitive needed, and problem 1406 builds that: from the truncating quotient, subtract 1 when the division is inexact and the signs differ.
Equivalently, and this is what the references use directly, add 1 to the truncating quotient exactly when the division is inexact and the signs agree.
## Why it is correct
If the division is exact there is nothing to round and both forms return the quotient. If it is inexact, the true value lies strictly between two consecutive integers. Truncation moves toward zero. When the signs agree the true quotient is positive, so truncation moved down and the ceiling is one higher. When the signs differ the true quotient is negative, so truncation moved up, which is already the ceiling and nothing is added. Those are all the cases.
## Overflow
|a| and |b| reach 10^18, so the inputs need 64 bits; a signed 32-bit
integer stops at 2147483647 and a 32-bit build answers -495539541 where the
truth is 333333333333333334. Note that the popular (a + b - 1) / b form
overflows even in 64 bits when a and b are both near 10^18, which is
a second reason to prefer the identity above: the corrected quotient never
leaves the range the plain division already occupied. In JavaScript 10^18 is
past 2^53, so BigInt is required, and BigInt division truncates toward zero
exactly as C does.
## Cost
O(1) per query.
Constraints - `1 ≤ q ≤ 1000` - `-1000000000000000000 ≤ a ≤ 1000000000000000000` - `-1000000000000000000 ≤ b ≤ 1000000000000000000` - `b` is not 0
Input
The first line contains q.
Each of the next q lines contains a and b, with b never 0.
Output
For each query print ceil(a / b), one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.