Алгоритмы и структуры данных

Бинарное возведение в степень

Дано 3 числа x, n и m. Необходимо вычислить результат выражения .

Входные данные

В единственной строке входных данных содержатся 3 целых числа x, n и m (1 ≤ x, n, m ≤ ).

Выходные данные

Программа должна вывести результат выражения .

Примеры

Входные данные
Выходные данные
2 10 5
4

Пояснение

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

Разбор задачи

Поскольку все числа могут быть довольно большими, нужен быстрый алгоритм, чтобы он работал достаточно быстро. Бинарное возведение в степень (binary exponentiation) — это эффективный способ вычислять большие степени числа. Оно сокращает количество умножений, необходимых для возведения в степень, что делает его быстрее традиционного метода, при котором мы просто умножаем результат на x в цикле от 1 до n.
 
Алгоритм бинарного возведения в степень основан на следующем принципе: если возвести число x в степень n, то можно представить так:
  • , если n чётно
  • , если n нечётно
Благодаря этому мы можем вычислить один раз и затем умножить результат на себя же, что значительно ускоряет процесс. Таким образом, алгоритм может выглядеть так:
def binpow(x, n, m):
    if n == 0:                        # Базовый случай: x^0 = 1
        return 1
    if n % 2 == 0:                    # n чётно => вычисляем половину и умножаем
        half = binpow(x, n // 2, m)   # вычисляем половину
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # n нечётно => res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Используя бинарное возведение в степень, мы снижаем время работы алгоритма с до , ведь при каждом шаге для чётного n мы делим показатель степени пополам. Важно, что при операции с нечётным n следующий шаг всегда будет с чётным n.
Рассмотрим, как алгоритм работает на нескольких значениях:
x = 2, n = 10 (мы не учитываем m для простоты)
  1. [n = 10] → n % 2 == 0 ⇒ вычисляем binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ вычисляем binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ вычисляем 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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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