In many cases, we are not interested in the absolute value of computations but rather in the result of a computation modulo
m(the remainder of the result after dividing it by
Interestingly enough, we actually deal with modular arithmetic every day. Whenever we look at our watches to find out the hour of the day, we are not interested in the time passed since the start of the year (or the time passed since the big bang) - but rather only the hour of the day. Which is the number of hours passed since the beginning of the year modulo
24depending on which one we’re interested in. So, as time goes on, the clock turns from 0 to 1, then to 2, to 3, …, up until getting to 11, and resets to 0 again. This process repeats itself infinitely as time goes on. The numbers are always in the range between 0 and 11. Given an arbitrary number of hours passed since the start of a year
h, we can find out the current hour of the day with
h % 12(remainder of
hdivided by 12).
When dealing with the last digit of a number, we can think of it as a “clock” with 10 hour-points - 0, 1, 2, … 9 that represent all the possible digits. As we add 1 to a number, the last digit is increased by 1 up until getting to 9 and as soon as we add another 1, the last digit resets to 0. Given an arbitrary number
n, we can find out its last digit with
n % 10(remainder of
ndivided by 10).
When working with bits (0s and 1s), we can think of a “clock” with only 2 hour-points - 0 and 1. If we add 1 to 0, it turns to 1. If we add 1 to 1, it turns to 0. Given an arbitrary bit-string number
n, we can find out its last bit with
n % 2(remainder of
ndivided by 2).
So, modular arithmetic is nothing more than a clock with
mis 12 for hours,
mis 10 for digits, and
mis 2 when working with bits).
mcan be an arbitrary number and in some problems, it’s required to calculate the result modulo some large prime number like . This number is usually chosen to make sure the computations cannot be skipped and are actually done properly.
When adding two numbers
b, we can be interested only in the result modulo
m. For instance, if we compute the last digit of the sum of
b, we are only interested in the result modulo
10. Yet, we can make the computation even easier by first computing the result of
m(getting the last digits for both numbers in this case) and then adding those together and computing the result modulo
m, which will make the computations way simpler
res = (a % m + b % m) % m:
We can think of subtraction
mas rolling back the clock
bunits starting from the time
a. Roll back the clock from 5 by 2 hours
(5 - 2) % 12 = 3or roll back the clock from 5 by 7 hours
(5 - 7) % 12 = -2 % 12 = 10. We can also subtract numbers larger than
mby first taking the modulo
mof those numbers:
(21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:
In some languages (like Python) the remainder operator
%is implemented in a way that always results in a positive number. Yet in other languages (like C++), this might not be the case. Therefore, for those languages, we need to add
mto the final result if it turns negative (add 12 to -2 which will result in 10). This intuitively means rolling the clock forward by one day (which doesn’t change the hour displayed on the clock).
When multiplying two numbers modulo
m, the result can be taken modulo
mis 10, we can think of it as finding out the last digit after multiplying two numbers together:
The division is more challenging than all the other operations. If we think of the last digit again, when dividing 28 by 7, we get 4 ⇒ the last digit of the result is 4. Yet, when taking the last digit of 28, which is 8, and the last digit of 7, which is 7, it isn’t obvious how to get 4 by dividing those two numbers. It’s possible to compute division modulo
musing Euler’s theorem. A more detailed explanation can be found here: https://cp-algorithms.com/algebra/module-inverse.html
Challenge: Calculate the power modulo
You are asked to calculate the value of
mare provided in the input.
The input contains a tree integers
n(1 ≤ n ≤ ), and
m(1 ≤ x, m ≤ ).
The program should print the result of
2 6 10
3 2 4
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB