Binary Exponentiation
Practice this coding question on Coding Gurukul.
Problem statement
For each query a b m, compute a raised to the power b, modulo m, using binary exponentiation. Use repeated squaring instead of multiplying a by itself b times. Reduce intermediate results modulo m. Define a^0=1, including 0^0. If m=1, the answer is always 0. Use integer arithmetic and O(log(b+1)) time per query. Signed 64-bit intermediate products are sufficient for the given bounds. Worked example 2^10=1024, so its remainder modulo 1000 is 24. 5^0 modulo 7 is 1. Any value modulo 1 is 0.
Input format
First line: q. Next q lines: a b m.
Output format
Print one modular power per line.
Constraints
1 <= q <= 10000; 0 <= a <= 10^9; 0 <= b <= 10^18; 1 <= m <= 10^9.
Sample input
3 2 10 1000 5 0 7 9 9 1
Sample output
24 1 0
Sign in to run or submit a solution in C++, Java or Python.