Given 3 numbers x, n, and m, you are asked to calculate the result of .
The only line of the input contains 3 integers x, n, and m (1 ≤ x, n, m ≤ ).
The program should print the result of the expression.
2 10 5
2^10 = 1024 ⇒ 1024 mod 5 = 4
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
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.