245. Modular Power
A cipher scrambles a message by raising a key a to a secret exponent b and keeping only the remainder after division by the prime 1000000007. Return a^b mod 1000000007.
Both numbers can be as large as 9 * 10^15, so computing a^b directly, or multiplying a by itself b times, is impossible. Reduce a modulo the prime first, then use repeated squaring on the bits of b, taking the remainder after every multiplication. Use the convention that 0^0 = 1, and note that a may itself be a multiple of 1000000007, giving 0 whenever b > 0.
Intended complexity is O(log b) multiplications with O(1) extra space. Be careful in languages without 64-bit-safe integers: JavaScript numbers lose precision above 2^53, so use BigInt there.
Example 1
- Input:
- a = 7, b = 222
- Output:
- 286423514
- Explanation:
7 raised to the 222nd power, reduced modulo 1000000007, is 286423514.
Example 2
- Input:
- a = 4000000031, b = 5
- Output:
- 243
- Explanation:
Since 4000000031 leaves remainder 3 modulo 1000000007, the answer is 3^5 = 243.
Constraints
0 ≤ a ≤ 9 * 1015
0 ≤ b ≤ 9 * 1015
The modulus is 1000000007 and the result is in [0, 1000000006].
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log b)
- Space
- O(1)