¿Cómo podemos encontrar (a ^ b)% c en complejidad mínima?

Answer 1

Primera observación: cada vez que multiplicas, debes reducir el mod c. Esto evitará que sus números sean demasiado grandes (en términos de número de dígitos). Ese algoritmo se vería así:

def exp_mod(a, b, c): ans = 1 for i from 1 to b: ans = (ans * a) % c return ans 

Esto requiere un total de b multiplicaciones. Sin embargo, podemos hacerlo mejor. Al escribir b en binario (es decir, como la suma de las potencias de 2), podemos escribir [matemáticas] a ^ b [/ matemáticas] como producto de alguna potencia de 2 potencias de a. Por ejemplo

[matemáticas] a ^ {91} = a ^ {64} \ cdot a ^ {32} \ cdot a ^ 8 \ cdot a ^ 2 \ cdot a [/ math]

En general, podemos escribir [matemáticas] a ^ b [/ matemáticas] como [matemáticas] O (\ log b) [/ matemáticas] multiplicaciones como esta. Y también podemos calcular las potencias de 2 potencias en multiplicaciones [matemáticas] O (\ log b) [matemáticas] usando el cuadrado repetido:

[matemáticas] a ^ 2 = a \ cdot a [/ matemáticas]
[matemáticas] a ^ 4 = a ^ 2 \ cdot a ^ 2 [/ matemáticas]
[matemáticas] a ^ 8 = a ^ 4 \ cdot a ^ 4 [/ matemáticas]

Nuevamente, para cada multiplicación, deberíamos hacer una operación de módulo para evitar que los números sean demasiado altos. Usando la cuadratura repetida terminamos con [math] O (\ log b) [/ math] multiplicación y operaciones de módulo.

Answer 2

Bueno, la solución a continuación se centra principalmente en una idea simple :

  int pow (int a, int b, int c) {
     if (b == 0) devuelve 1;  // a ^ 0 = 1
     más si (b == 1) devuelve a;  // a ^ 1 = a
     más si (b & 1) devuelve (a * pow (a, b-1, c))% c;  // cuando b es impar
     más retorno (pow (a, b / 2, c) * pow (a, b / 2, c))% c;  // cuando b es par 
 }

El mismo enfoque también se puede implementar utilizando operadores bit a bit, ya que funcionan de manera muy eficiente a nivel de registro.

  #define mod 10000000007
 int pow (int a, int b) {
     si (! b) devuelve 1;
     if (b == 1) devuelve a;
     int q = pow (a, b >> 1);
     q = (q * q)% mod;
     si (b & 1) q = (q * a)% mod;
     volver q;
 }

La relación de recurrencia para ambas soluciones se aproxima a: [matemática] T (n) <= T (n / 2) + 1 [/ matemática] (Cuando b es impar, se reduce en uno y cuando b es par, se reduce en n / 2) que al resolver nos da una solución [matemática] O (log (n)) [/ matemática].

  # Implementación de Python
 def pow_mod (x, y, z):
     ans = 1
     mientras y:
         si y & 1:
             ans = ans * x% z
         y >> = 1
         x = x * x% z
     volver ans

Answer 3

Puede usar el teorema de Euler, pero hay ciertas reglas básicas para usar este teorema.
Reglas de juego:
(a ^ b)% c-
1) En esta expresión, ‘a’ y ‘c’ deben ser números primos (que significa ‘a’ y ‘c’ no deberían tener factores comunes excepto 1).
2) El número de números primos para el número ‘c’ debe ser igual a ‘b’.

Entonces (a ^ b)% c es igual a 1.

Por ejemplo: (5 ^ 6)% 7 = 1

Answer 4

Como (a * b)% c = (a% c * b% c)% c
si un% c se reduce a un número distinto de a (es decir, a> c), entonces
podemos escribir (a ^ b)% c = ((a% c) ^ b)% c

de lo contrario, encuentre a ^ x tal que a ^ x sea simplemente mayor que c, por ejemplo. 2 ^ 6% 5 = (2 ^ 3% 5) ^ 2% 5
aquí 2 ^ 3 es mayor que 5, entonces la exorestación se reduce a 3 ^ 2% 5 aplica el mismo proceso nuevamente. => comienza con 3 y fing la potencia de 3> 5 obtenemos 3 ^ 2> 5 y luego usamos el módulo produciendo la respuesta = 4;

Espero haberte dicho el algoritmo.