Модульная арифметика
Во многих задачах нас интересует не само абсолютное значение результата вычислений, а лишь результат вычисления по модулю
m (то есть остаток от деления результата на m).На самом деле, с модульной арифметикой мы сталкиваемся ежедневно. Когда мы смотрим на часы, чтобы узнать, который сейчас час, нас не волнует, сколько времени прошло с начала года (или со времён Большого взрыва) — мы хотим знать лишь текущее значение на циферблате. Это число часов, прошедших с начала года, по модулю
12 или 24 (в зависимости от наших предпочтений). Со временем часы последовательно показывают 0, 1, 2, 3, …, доходят до 11, а затем снова сбрасываются на 0. Так этот цикл повторяется бесконечно. Часы всегда показывают значения в диапазоне от 0 до 11. Если дано некое количество часов h, прошедших с начала года, определить текущий час дня можно, посчитав h % 12 (остаток от деления h на 12).
Если говорить о последней цифре числа, то можно представить себе «часы» с 10 «часовыми делениями» — 0, 1, 2, …, 9, которые соответствуют всем возможным цифрам. При добавлении 1 к числу, его последняя цифра увеличивается на 1, доходя до 9, а потом при очередном добавлении 1 снова обнуляется до 0. Для произвольного числа
n мы можем узнать его последнюю цифру, вычислив n % 10.При работе с битами (0 и 1) такие «часы» имеют всего 2 «деления» — 0 и 1. Если мы к 0 прибавляем 1, получаем 1. Если мы к 1 прибавляем 1, снова получаем 0. Для произвольного битового числа
n последним битом будет n % 2.Таким образом, модульная арифметика — это не что иное, как воображаемые часы с
m делениями (где m может быть 12 для часов, 10 для цифр или 2 для битов). Параметр m может принимать любое значение, и во многих задачах нас просят вычислять результат по модулю какого-нибудь большого простого числа, например . Такое число часто выбирают для того, чтобы результаты вычислений нельзя было просто «пропустить» и приходилось считать их корректно.Addition modulo m (Сложение по модулю m)
При сложении двух чисел
a и b нас может интересовать лишь результат по модулю m. Например, если мы ищем последнюю цифру суммы a и b, то нас интересует результат по модулю 10. При этом вычисления можно упростить, сначала взяв a по модулю m, затем b по модулю m (то есть взять последнюю цифру каждого), а потом сложить их и снова взять результат по модулю m. Это облегчает вычисление: res = (a % m + b % m) % m:Subtraction modulo m (Вычитание по модулю m)
Вычитание
b из a по модулю m можно представить как отмотку «часов» на b делений, начиная с показания a. Например, если мы отматываем часы от 5 на 2 деления, получаем (5 - 2) % 12 = 3. Если отматываем от 5 на 7 — (5 - 7) % 12 = -2 % 12 = 10. Можно вычитать и числа, превышающие m, взяв их по модулю m до вычитания: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:В некоторых языках программирования (например, Python) оператор остатка
% всегда возвращает неотрицательное число, а в других (например, C++) — может и отрицательное. Поэтому в таких языках нужно добавлять m, если результат получился отрицательным (в случае -2 по модулю 12 нужно добавить 12, чтобы получить 10). Интуитивно это похоже на то, что мы переводим часы на сутки вперёд (что не меняет отображаемое время).Multiplication modulo m (Умножение по модулю m)
При умножении двух чисел по модулю
m результат также можно взять по модулю m. Если m равно 10, то мы ищем последнюю цифру произведения двух чисел:Division modulo m (Деление по модулю m)
Деление по модулю
m сложнее остальных операций. Используя пример с последней цифрой, при делении 28 на 7 мы получаем 4, значит последняя цифра результата — 4. Но если мы возьмём последнюю цифру 28, то есть 8, и последнюю цифру 7, то есть 7, то сразу непонятно, как получить 4 при делении 8 на 7. Чтобы выполнить деление по модулю m, можно воспользоваться теоремой Эйлера. Более детальное объяснение есть по ссылке: https://cp-algorithms.com/algebra/module-inverse.htmlChallenge: Calculate the power modulo m (Задача: вычислить степень по модулю m)
Требуется вычислить значение , где
x, n и m заданы во входных данных.Входные данные
Вход содержит три числа
x, n (1 ≤ n ≤ ) и m (1 ≤ x, m ≤ ).Выходные данные
Программа должна вывести результат вычисления .
Примеры
Input | Output |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB