Practice › Basics
Power with Modulo
Medium · Basics · Asked at Google, Amazon, Microsoft
Compute a^b mod m.
Input
One line with a b m.
Output
The value of a^b mod m.
Constraints
- 0 ≤ a ≤ 10^9
- 0 ≤ b ≤ 10^18
- 1 ≤ m ≤ 10^9
b is huge — use fast (binary) exponentiation in O(log b). Note a^0 = 1, and anything mod 1 is 0.
Example 1
Input
2 10 1000
Output
24
Example 2
Input
3 0 7
Output
1
Hints
- Multiplying a by itself b times is far too slow when b is 10^18.
- Binary exponentiation: a^b = (a²)^(b/2), times one extra a when b is odd. Take mod after every multiplication.
Approach
Fast exponentiation looks at the bits of b. Keep base = a mod m and result = 1 mod m. While b > 0: if the lowest bit of b is set, multiply result by base; then square base and shift b right. Every product is below 10^18 because both factors are below m ≤ 10^9, so 64-bit integers are enough. Starting with 1 % m makes the m = 1 case print 0.
Complexity: O(log b) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b, m;
cin >> a >> b >> m;
long long result = 1 % m, base = a % m;
while (b > 0) {
if (b & 1) result = result * base % m;
base = base * base % m;
b >>= 1;
}
cout << result << "\n";
return 0;
}Python solution
a, b, m = map(int, input().split())
# Python's built-in pow does fast modular exponentiation
print(pow(a, b, m))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong(), b = sc.nextLong(), m = sc.nextLong();
long result = 1 % m, base = a % m;
while (b > 0) {
if ((b & 1) == 1) result = result * base % m;
base = base * base % m;
b >>= 1;
}
System.out.println(result);
}
}