A introdução de um algoritmo de módulo de potência rápido é proposto pelas limitações de um algoritmo ingênuo que leva módulo dos decimais de grandes números. No método ingênuo, calculamos um número como 5^1003%31, o que consome muito nossos recursos de computação. A coisa mais problemática em todo o processo de cálculo é o nosso processo de 5^1003.
Desvantagem 1: No processo de calcular o índice posteriormente, os números calculados não são todos aumentados, o que ocupa muitos de nossos recursos de computação (principalmente tempo e espaço)
Desvantagem 2: Os números em nosso cálculo são tão grandes que nossos computadores existentes não podem registrar dados tão longos; portanto, devemos pensar em uma maneira mais eficiente de resolver esse problema.
Quando calculamos AB%C, a maneira mais conveniente é chamar o método PoW na função de matemática. No entanto, às vezes o número de A ao poder de B é muito grande, e até a dupla dupla de precisão será transbordada. Neste momento, para obter o resultado do AB%C, optaremos por usar o algoritmo rápido do módulo de energia para obter o resultado que queremos de maneira simples e rápida.
Para impedir que os números transbordem e reduzam a complexidade, precisamos usar a seguinte fórmula:
abmod c = (um mod c) bmod c
O significado desta fórmula é: o produto leva o restante igual ao produto, leva o restante. É fácil ver que essa fórmula é transitiva, para que possamos tornar um cada vez menor, tomando o restante constantemente para evitar transbordamento.
Teoricamente, com esta fórmula, podemos escrever código. Ao modular constantemente a, garantimos que o resultado não transborque. Isso pode de fato calcular o módulo de uma potência para uma potência maior, mas a complexidade desse método ainda é O (n) e não é rápida.
Para calcular o módulo de um poder mais rapidamente, também precisamos confiar na seguinte fórmula:
ab mod c = (a2) b/2 mod c, b é um número par
ab mod c = ((a2) b/2 ・ a) mod c, b é um número ímpar
Esta fórmula é muito simples. O princípio é substituir constantemente B pelo quadrado de A e substituir B pela metade original. Porque sabemos através da primeira fórmula que o módulo de um número tem a mesma potência (essa frase é um pouco confusa, o que significa Fórmula 1). Então, o efeito de usar o resultado de A*A%C em vez de A é o mesmo.
Portanto, de acordo com a fórmula acima, obtemos um método para calcular a potência rápida com a complexidade O (logn):
importar java.util.scanner; public class Main {public static void main (string [] args) {scanner in = new scanner (system.in); int a = in.nextInt (), b = in.nextInt (), c = in.nextInt (); int res = 1; a %= c; para (; b! = 0; b /= 2) {if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } System.out.println (res); }}Este algoritmo é aproximadamente assim. A primeira etapa é reduzir um%= c para impedir que o número transborda quando A*A é realizado pela primeira vez. No loop for, se B é um número ímpar, deixe res = res*a e, em seguida, multiplique um resultado primeiro e depois o processe. Para impedir que o número seja transbordante, o Mod C de Res*é é operado diretamente. Nisso para loop, mais cedo ou mais tarde, B será igual a 1, insira a ramificação IF e, finalmente, calcule o valor de res e mod c, sai do loop for e, em seguida, o resultado final.
Resumir
O exposto acima é toda a explicação detalhada deste artigo sobre a implementação do algoritmo Fast Power Modulus do idioma Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!