Aritmética modular
Em muitos casos, não interessa o valor absoluto de um cálculo, mas sim o resultado desse cálculo módulo
m (ou seja, o resto depois de dividir o resultado por m).Curiosamente, lidamos com aritmética modular todos os dias. Sempre que olhamos para o relógio para saber as horas, não estamos interessados no tempo que passou desde o início do ano (ou desde o Big Bang), mas apenas nas horas do dia. Isso corresponde ao número de horas desde o começo do ano tomado módulo
12 ou 24, consoante o formato. Assim, à medida que o tempo avança, o relógio passa de 0 para 1, depois para 2, 3, …, até chegar a 11, e então volta a 0. Este ciclo repete-se infinitamente. Os números estão sempre entre 0 e 11. Dado um número arbitrário de horas decorridas desde o início de um ano h, podemos saber a hora do dia atual calculando h % 12 (o resto de h por 12).
Quando observamos apenas o último dígito de um número, podemos imaginar um “relógio” com 10 posições – 0, 1, 2, …, 9 – que representam todos os possíveis algarismos. À medida que somamos 1 a um número, o último dígito aumenta em 1 até chegar a 9; logo que lhe adicionamos mais 1, o último dígito volta a ser 0. Dado um número arbitrário
n, para descobrir o seu último dígito basta calcular n % 10 (o resto de n por 10).Quando trabalhamos com bits (0s e 1s), podemos imaginar um “relógio” com apenas 2 posições – 0 e 1. Se adicionarmos 1 a 0, este passa para 1. Se adicionarmos 1 a 1, ele volta a 0. Dada uma representação em bits de um número
n, podemos descobrir o seu último bit calculando n % 2 (o resto de n por 2).Portanto, a aritmética modular não é mais que um relógio com
m posições (onde m é 12 para as horas, 10 para os dígitos e 2 para bits). O valor de m pode ser qualquer número, e em certos problemas é preciso calcular o resultado módulo de um número primo grande, como . Esta escolha costuma ser feita para garantir que os cálculos não sejam trivialmente contornados e sejam efetuados corretamente.Adição módulo m
Sempre que somamos dois números
a e b, podemos estar interessados apenas no resultado módulo m. Por exemplo, se só queremos o último dígito da soma de a e b, estamos a olhar para o resultado módulo 10. Contudo, para simplificar, podemos primeiro calcular o resultado de a e b cada um módulo m (no caso, os últimos dígitos de cada) e só depois somar esses valores, voltando a tirar módulo m. Isso torna a conta mais simples: res = (a % m + b % m) % m:Subtração módulo m
Podemos encarar a subtração de
b a a módulo m como recuar o “relógio” b posições a partir de a. Por exemplo, recuar o relógio de 5 em 2 horas dá (5 - 2) % 12 = 3, ou recuar o relógio de 5 em 7 horas dá (5 - 7) % 12 = -2 % 12 = 10. Também é possível subtrair números maiores do que m ao usar a sua forma módulo m primeiro: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:Em algumas linguagens (como Python), o operador de resto
% é implementado de forma a devolver sempre um número positivo. Noutras (como C++), isso pode não acontecer. Por isso, nestas linguagens, se o resultado for negativo, precisamos de somar m ao valor final (como somar 12 a -2 para obter 10). Isso corresponde, intuitivamente, a avançar o relógio um ciclo completo (o que não altera a hora que ele mostra).Multiplicação módulo m
Ao multiplicar dois números módulo
m, o resultado final também pode ser tomado módulo m. Se m for 10, isso equivale a verificar qual o último dígito após a multiplicação de dois números:Divisão módulo m
A divisão é mais complicada que as outras operações. Se pensarmos novamente no último dígito, ao dividir 28 por 7 obtemos 4 ⇒ o último dígito do resultado é 4. Mas se formos ver apenas o último dígito de 28 (que é 8) e de 7 (que é 7), não fica óbvio como chegar a 4 dividindo esses dois algarismos. É possível efetuar divisão módulo
m usando o teorema de Euler. Uma explicação mais detalhada pode ser encontrada aqui: https://cp-algorithms.com/algebra/module-inverse.htmlDesafio: Calcular a potência módulo m
É pedido que calcule o valor de , onde
x, n e m são fornecidos na entrada.Entrada
A entrada contém três inteiros
x, n (1 ≤ n ≤ ) e m (1 ≤ x, m ≤ ).Saída
O programa deve apresentar o resultado de .
Exemplos
Entrada | Saída |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB