Skills101
← All coding problems

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 q lines: three integers a 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).

Loading editor…

Log in to run and submit your code — it's free.