Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Binary Exponentiation

    Given 3 numbers x, n, and m, you are asked to calculate the result of .

    Input

    The only line of the input contains 3 integers x, n, and m (1 ≤ x, n, m ≤ ).

    Output

    The program should print the result of the expression.

    Examples

    Input
    Output
    2 10 5
    4

    Explanation

    1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
     

    Tutorial

    As all the numbers are pretty large, we need to use a fast algorithm to make sure it’s quick enough. 1. Binary exponentiation is an efficient way of computing large powers of a number. It reduces the number of multiplications required to compute the power, which makes it faster than the traditional method of looping from 1 through n and multiplying the result by x.
     
    The binary exponentiation algorithm is based on the following mathematical observation: if we have a number x raised to the power of n, then can be represented as:
    • if n is even
    • if n is odd
    This actually makes the process of calculating the way faster as we can calculate the once and then multiply the result twogether. So, the algorithm can look like this:
    def binpow(x, n, m):
        if n == 0:                        # Base case: x^0 = 1
            return 1
        if n % 2 == 0:                    # n is even => calculate half and multiply
            half = binpow(x, n // 2, m)   # calculate the half
            return (half * half) % m      # res = x^(n/2) * x^(n/2)
    
        # n is odd => res = x * x^(n-1)
        return (x * binpow(x, n - 1, m)) % m
    With binary exponentiation, we reduce the time complexity from operations to as we split n on every iteration where n is even. It’s important to note that for each operation where n is odd, for the next iteration n is even.
    Let’s simulate the algorithm on several inputs:
    x = 2, n = 10 (we discard m for simplicity)
    1. [n = 10] → n % 2 == 0 ⇒ calculate binpow(2, 5)
    1. [n = 5] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 4)
    1. [n = 4] → n % 2 == 0 ⇒ calculate binpow(2, 2)
    1. [n = 2] → n % 2 == 0 ⇒ calculate binpow(2, 1)
    1. [n = 1] ⇒ n % 2 ≠ 0 ⇒ return 2 * binpow(2, 0)
    1. [n = 0] ⇒ n == 0 ⇒ return 1
    1. [up to n = 1] ⇒ return 2 * 1 = 2
    1. [up to n = 2] ⇒ return 2 * 2 = 4
    1. [up to n = 4] ⇒ return 4 * 4 = 16
    1. [up to n = 5] ⇒ return 2 * 16 ⇒ 32
    1. [up to n = 10] ⇒ return 32 * 32 = 1024
     
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue