Modular arithmetic
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 m). 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
12 or 24 depending 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 h divided 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 n divided 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 n divided by 2).So, modular arithmetic is nothing more than a clock with
m points (m is 12 for hours, m is 10 for digits, and m is 2 when working with bits). m can 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.Addition modulo m
When adding two numbers
a and b, we can be interested only in the result modulo m. For instance, if we compute the last digit of the sum of a and b, we are only interested in the result modulo 10. Yet, we can make the computation even easier by first computing the result of a modulo m, then b modulo 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:Subtraction modulo m
We can think of subtraction
b from a modulo m as rolling back the clock b units starting from the time a. Roll back the clock from 5 by 2 hours (5 - 2) % 12 = 3 or roll back the clock from 5 by 7 hours (5 - 7) % 12 = -2 % 12 = 10. We can also subtract numbers larger than m by first taking the modulo m of 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 m to 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).Multiplication modulo m
When multiplying two numbers modulo
m, the result can be taken modulo m. If m is 10, we can think of it as finding out the last digit after multiplying two numbers together:Division modulo m
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
m using Euler’s theorem. A more detailed explanation can be found here: https://cp-algorithms.com/algebra/module-inverse.htmlChallenge: Calculate the power modulo m
You are asked to calculate the value of
x, n, and m are provided in the input.Input
The input contains a tree integers
x, n (1 ≤ n ≤ ), and m (1 ≤ x, m ≤ ).Output
The program should print the result of
Examples
Input | Output |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB