Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Multiplying a by itself b times is far too slow when b is 10^18.
  2. 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);
    }
}

Solve Power with Modulo online · All practice problems