Modular Exponentiation
mediumMath & Number Theory+20 XPTime limit 2s
Compute a^b mod m — the remainder when a raised to the power b is divided by m. The exponent can be as large as 10¹⁸, so multiplying a by itself b times is far too slow.
Input:
- line 1:
q - next
qlines: three integersa b m
Output: q lines — the value of a^b mod m (a number from 0 to m − 1). Note that a⁰ = 1, so the answer for b = 0 is 1 mod m.
Constraints: 1 ≤ q ≤ 10⁴, 0 ≤ a ≤ 10¹⁸, 0 ≤ b ≤ 10¹⁸, 1 ≤ m ≤ 10⁹.
Think about it: binary exponentiation (square-and-multiply). Write b in binary: square a at every step and multiply it into the answer when the current bit is 1 — about 60 steps. Reduce a mod m first and take % m after every multiplication so the products fit in 64 bits.
Sample input 1
3 2 10 1000 3 0 7 5 3 13
Sample output 1
24 1 8
Sample input 2
1 2 1000000000000000000 1000000007
Sample output 2
719476260
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).