Print a to the power b, modulo m. Here a^0 is 1, even when a is 0. The exponent can be huge, so multiplying a by itself b times is far too slow.
What to build
A fast power program using repeated squaring.
Requirements
- Keep every intermediate value below
mby taking the remainder. - Use
long longfor the multiplications. - Make sure
m = 1gives 0.
Input
One line with a, b and m (0 ≤ a ≤ 1,000,000,000, 0 ≤ b ≤ 10^18, 1 ≤ m ≤ 1,000,000,000).
Output
a^b mod m.
Constraints
0 ≤ a ≤ 1,000,000,000, 0 ≤ b ≤ 10^18 and 1 ≤ m ≤ 1,000,000,000.
Example
Input:
2 10 1000
Output:
24
Why it works
The binary digits of b say which squares of a to multiply together, so only about log₂ b steps are needed, around 60 for the largest b.
Examples
Example 1 · Input
2 10 1000
Expected output
24
Example 2 · Input
3 13 1000
Expected output
323
Hints
Hint 1
Multiplying b times is far too slow for b = 10^18; use repeated squaring.
Hint 2
While b > 0: if b is odd, result = result * a % m; then a = a * a % m and b /= 2.
Hint 3
Start with result = 1 % m, so that m = 1 gives 0.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
long long power_mod(long long a, long long b, long long m) {
long long result = 1 % m;
a %= m;
while (b > 0) {
if (b % 2 == 1) result = result * a % m;
a = a * a % m;
b /= 2;
}
return result;
}
int main(void) {
long long a, b, m;
scanf("%lld %lld %lld", &a, &b, &m);
printf("%lld\n", power_mod(a, b, m));
return 0;
}