1606. A Huge Power, Modulo Something
For each of q queries, given a, b and m, print a to the power b,
taken modulo m.
a = 2, b = 10, m = 1000000007 -> 1024
a = 3, b = 0, m = 7 -> 1
a = 5, b = 1, m = 13 -> 5
a = 2, b = 1, m = 2 -> 0
By convention a to the power 0 is 1, and that 1 is then taken modulo m, so
with m = 1 the answer is 0.
## What most people try first
Multiply b times. Correct, and O(b) per query: with b up to 10^9 and
10^5 queries that is 10^14 multiplications.
Computing a to the power b first and then taking the modulus is worse than
slow, it is impossible. 2 to the power 10^9 has about 300 million digits.
The modulus has to be applied at every step, not at the end.
## Halve the exponent
a^b = (a^(b/2))^2 when b is even
a^b = a * a^(b-1) when b is odd
a^0 = 1
Each step either halves b or makes it even, so the exponent reaches 0 in at
most 2 log2(b) steps: about 60 for b = 10^9, against a billion.
Written as a loop rather than a recursion, this reads the exponent's binary digits from the bottom:
result = 1; base = a mod m
while b > 0:
if b is odd: result = result * base mod m
base = base * base mod m
b = b / 2
## Why reading the bits is the same thing
b is a sum of distinct powers of two, so a^b is the product of a^(2^i) over
the set bits i. The loop keeps base equal to a^(2^i) at step i by
squaring it each time, and multiplies it in exactly when bit i is set. The
recursive halving and the bit loop are the same computation written two ways.
## The multiplication is where this breaks
With m up to 10^9, both result and base are below 10^9, so their
product reaches 10^18. That FITS in a signed 64 bit integer, whose limit is
about 9.2 * 10^18, but it does NOT fit in 32 bits, and a 32 bit multiply here
wraps to an arbitrary value that then propagates through every later step.
So the multiplication must be done in 64 bits in C, C++ and Java. In JavaScript
10^18 is past the 2^53 where doubles stay exact, so the reference there uses
BigInt rather than Number.
## The boundaries
b = 0 answers 1 mod m. m = 1 makes every answer 0, including the b = 0
case, which is why the result starts at 1 % m rather than at 1. Both are
declared tests, and the m = 1 case is the one most solutions get wrong.
## Cost
O(log b) multiplications per query, about 30 iterations at b = 10^9, so
3 * 10^6 across 10^5 queries.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ a ≤ 10^9` - `0 ≤ b ≤ 10^9` - `1 ≤ m ≤ 10^9` - `a` to the power 0 is 1, then reduced modulo `m`
Input
The first line contains the integer q.
Each of the next q lines contains three integers a, b and m.
Output
Print one integer on its own line for each query, in the order given: a raised to the power b, taken modulo m, which is 0 whenever m is 1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.