La introducción de un algoritmo de módulo de potencia rápida se propone por las limitaciones de un algoritmo ingenuo que toma el módulo de los decimales de grandes números. En el método ingenuo, calculamos un número como 5^1003%31, lo que consume mucho nuestros recursos informáticos. Lo más problemático en todo el proceso de cálculo es nuestro proceso 5^1003.
Desventaja 1: en el proceso de calcular el índice más adelante, los números calculados no aumentan, lo que ocupa muchos de nuestros recursos informáticos (principalmente tiempo y espacio)
Desventaja 2: Los números en nuestro cálculo son tan grandes que nuestras computadoras existentes no pueden registrar datos tan largos, por lo que debemos pensar en una forma más eficiente de resolver este problema.
Cuando calculamos AB%C, la forma más conveniente es llamar al método POW en la función matemática. Sin embargo, a veces el número de A al poder de B es demasiado grande, e incluso el doble de doble precisión se desbordará. En este momento, para obtener el resultado de AB%C, elegiremos usar el algoritmo de módulo de potencia rápida para obtener el resultado que queremos de manera simple y rápida.
Para evitar que los números se desborden y reduzcan la complejidad, necesitamos usar la siguiente fórmula:
abmod c = (un mod c) bmod c
El significado de esta fórmula es: el producto toma el resto igual al producto toma el resto. Es fácil ver que esta fórmula es transitiva, de modo que podamos hacer un cada vez más pequeño tomando constantemente el resto para evitar el desbordamiento.
Teóricamente, con esta fórmula, podemos escribir código. Al modular constantemente A, nos aseguramos de que el resultado no se desborde. De hecho, esto puede calcular el módulo de una potencia a una potencia mayor, pero la complejidad de este método aún es O (N) y no es rápida.
Para calcular el módulo de una potencia más rápidamente, también debemos confiar en la siguiente fórmula:
AB Mod C = (A2) B/2 Mod C, B es un número uniforme
AB Mod C = ((A2) B/2 ・ A) Mod C, B es un número impar
Esta fórmula es muy simple. El principio es reemplazar constantemente B con el cuadrado de A y reemplazar B con la mitad original. Porque sabemos a través de la primera fórmula que el módulo de un número tiene el mismo poder (esta oración es un poco confusa, lo que significa Fórmula Uno). Entonces el efecto de usar el resultado de A*a%C en lugar de A es el mismo.
Entonces, según la fórmula anterior, obtenemos un método para calcular la potencia rápida con complejidad O (logn):
import 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 es más o menos así. El primer paso es reducir un%= C para evitar que el número se desborde cuando A*A se realiza por primera vez. En el bucle for, si b es un número impar, deje res = res*a, y luego multiplique A en el resultado primero, y luego proceselo. Para evitar que el número se desborde, el resultado mod C de Res*A se opera directamente. En esto para el bucle, tarde o temprano, B es igual a 1, ingresará la rama IF y finalmente calculará el valor de Res y Mod C sale del bucle for, y luego el resultado final.
Resumir
Lo anterior es toda la explicación detallada de este artículo sobre la implementación del algoritmo de módulo de potencia rápida del lenguaje Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!