Aritmética modular
En muchos casos, no nos interesa el valor absoluto de los cálculos, sino más bien el resultado de esos cálculos módulo
m (el valor del residuo al dividir el resultado entre m).Curiosamente, lidiamos con la aritmética modular todos los días. Cada vez que miramos un reloj para saber la hora, no revisamos el tiempo transcurrido desde el inicio del año (o desde el Big Bang), sino solo la hora del día. Dicho de otro modo, nos interesa la cantidad de horas transcurridas desde el inicio del año módulo
12 o 24, según cuál estemos usando. A medida que el tiempo avanza, el reloj pasa de 0 a 1, luego a 2, 3, …, hasta llegar a 11 y vuelve a 0. Este proceso se repite continuamente conforme sigue transcurriendo el tiempo. Los valores siempre están entre 0 y 11. Dado un número arbitrario de horas transcurridas h, podemos obtener la hora actual del día con h % 12 (el residuo de dividir h entre 12).
Cuando nos enfocamos en el último dígito de un número, podemos pensarlo como un “reloj” con 10 marcas horarias: 0, 1, 2, …, 9, que representan todos los dígitos posibles. Al sumar 1 a un número, su último dígito aumenta en 1 hasta llegar a 9; en cuanto sumamos 1 más, el último dígito se reinicia a 0. Dado un número arbitrario
n, podemos conocer su último dígito con n % 10.Al trabajar con bits (0 y 1), podemos imaginar un “reloj” con solo 2 marcas: 0 y 1. Si sumamos 1 a 0, pasa a 1. Si sumamos 1 a 1, pasa a 0. Para un número binario cualquiera
n, su último bit se obtiene con n % 2.Entonces, la aritmética modular no es más que un reloj con
m posiciones (m es 12 para las horas, 10 para los dígitos y 2 al trabajar con bits). m puede ser cualquier número, y en algunos problemas se pide calcular el resultado módulo algún número primo grande como , el cual suele elegirse para asegurar que las operaciones no se puedan “evitar” y que realmente se realicen correctamente.Suma módulo m
Cuando sumamos dos números
a y b, a veces solo nos interesa el resultado módulo m. Por ejemplo, si buscamos el último dígito de a + b, nos basta el resultado módulo 10. Pero podemos simplificar la operación calculando primero a % m y b % m (en este caso, los últimos dígitos de ambos números) y luego sumarlos, para después volver a calcular el resultado módulo m: res = (a % m + b % m) % m:Resta módulo m
Podemos interpretar la resta de
b desde a módulo m como retroceder el reloj b unidades a partir de la posición a. Por ejemplo, retroceder 2 horas desde 5: (5 - 2) % 12 = 3, o retroceder 7 horas desde 5: (5 - 7) % 12 = -2 % 12 = 10. También es posible restar números más grandes que m al tomar primero el valor módulo de dichos números: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:En algunos lenguajes (como Python), el operador de residuo
% siempre produce un resultado positivo. En otros (como C++), esto puede no suceder. Por lo tanto, en esos lenguajes debemos agregar m al resultado final si es negativo (por ejemplo, sumar 12 a -2 para obtener 10). Esta idea equivale a adelantar el reloj un día completo (lo que no cambia la hora que se muestra).Multiplicación módulo m
Al multiplicar dos números módulo
m, el resultado se puede tomar nuevamente módulo m. Si m es 10, podemos pensarlo como obtener el último dígito tras multiplicar dos números:División módulo m
La división es más complicada que las demás operaciones. Volviendo al ejemplo del último dígito, si dividimos 28 entre 7, el resultado es 4 ⇒ el último dígito del resultado es 4. Sin embargo, tomar el último dígito de 28 (que es 8) y de 7 (que es 7) no hace evidente cómo llegar a 4 al dividir esos dos números. Es posible realizar divisiones módulo
m usando el teorema de Euler. Para una explicación más detallada, se puede consultar: https://cp-algorithms.com/algebra/module-inverse.htmlDesafío: Calcular la potencia módulo m
Se solicita calcular el valor de , donde
x, n y m se proporcionan en la entrada.Entrada
La entrada contiene tres enteros
x, n (1 ≤ n ≤ ) y m (1 ≤ x, m ≤ ).Salida
El programa debe imprimir el resultado de .
Ejemplos
Entrada | Salida |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB