Dados dos números base y exp , necesitamos calcular base exp en Modulo 10^9+7 Ejemplos:
Input : base = 2, exp = 2 Output : 4 Input : base = 5, exp = 100000 Output : 754573817
En las competiciones, para calcular grandes potencias de un número, se nos da un valor de módulo (un número primo grande) porque, a medida que se calculan los valores de, puede volverse muy grande, por lo que en su lugar tenemos que calcular ( % del valor del módulo). Podemos usar el módulo a nuestra manera ingenua usando módulo en todos los pasos intermedios y tomando módulo al final, pero en las competencias definitivamente mostrará TLE. Así que lo que podemos hacer. La respuesta es que podemos probar la exponenciación elevando al cuadrado , que es un método rápido para calcular la exponenciación de un número. Aquí discutiremos los dos métodos más comunes/importantes:
- Método básico (exponenciación binaria)
- -método ario.
Exponenciación binaria
Como se describe en este artículo, usaremos la siguiente fórmula para calcular de forma recursiva ( % del valor del módulo):
C++
// C++ program to compute exponential // value under modulo using binary // exponentiation. #include<iostream> using namespace std; #define N 1000000007 // prime modulo value long int exponentiation(long int base, long int exp) { if (exp == 0) return 1; if (exp == 1) return base % N; long int t = exponentiation(base, exp / 2); t = (t * t) % N; // if exponent is even value if (exp % 2 == 0) return t; // if exponent is odd value else return ((base % N) * t) % N; } // Driver Code int main() { long int base = 5; long int exp = 100000; long int modulo = exponentiation(base, exp); cout << modulo << endl; return 0; } // This Code is contributed by mits
Java
// Java program to compute exponential value under modulo // using binary exponentiation. import java.util.*; import java.lang.*; import java.io.*; class exp_sq { static long N = 1000000007L; // prime modulo value public static void main(String[] args) { long base = 5; long exp = 100000; long modulo = exponentiation(base, exp); System.out.println(modulo); } static long exponentiation(long base, long exp) { if (exp == 0) return 1; if (exp == 1) return base % N; long t = exponentiation(base, exp / 2); t = (t * t) % N; // if exponent is even value if (exp % 2 == 0) return t; // if exponent is odd value else return ((base % N) * t) % N; } }
Python3
# Python3 program to compute # exponential value under # modulo using binary # exponentiation. # prime modulo value N = 1000000007; # Function code def exponentiation(bas, exp): if (exp == 0): return 1; if (exp == 1): return bas % N; t = exponentiation(bas, int(exp / 2)); t = (t * t) % N; # if exponent is # even value if (exp % 2 == 0): return t; # if exponent is # odd value else: return ((bas % N) * t) % N; # Driver code bas = 5; exp = 100000; modulo = exponentiation(bas, exp); print(modulo); # This code is contributed # by mits
C#
// C# program to compute exponential // value under modulo using binary // exponentiation. using System; class GFG { // prime modulo value static long N = 1000000007L; // Driver code public static void Main() { long bas = 5; long exp = 100000; long modulo = exponentiation(bas, exp); Console.Write(modulo); } static long exponentiation(long bas, long exp) { if (exp == 0) return 1; if (exp == 1) return bas % N; long t = exponentiation(bas, exp / 2); t = (t * t) % N; // if exponent is even value if (exp % 2 == 0) return t; // if exponent is odd value else return ((bas % N) * t) % N; } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to compute exponential // value under modulo using binary // exponentiation. // prime modulo value $N = 1000000007; // Function code function exponentiation($bas, $exp) { global $N ; if ($exp == 0) return 1; if ($exp == 1) return $bas % $N; $t = exponentiation($bas, $exp / 2); $t = ($t * $t) % $N; // if exponent is // even value if ($exp % 2 == 0) return $t; // if exponent is // odd value else return (($bas % $N) * $t) % $N; } // Driver code $bas = 5; $exp = 100000; $modulo = exponentiation($bas, $exp); echo ($modulo); // This code is contributed by ajit ?>
Javascript
<script> // JavaScript program to compute // exponential value under // modulo using binary // exponentiation. // prime modulo value let N = 1000000007; // Function code function exponentiation(base, exp){ if (exp == 0){ return 1; } if (exp == 1){ return (base % N); } let t = exponentiation(base,exp/2); t = ((t * t) % N); console.log(t); // if exponent is // even value if (exp % 2 == 0){ return t; } // if exponent is // odd value else{ return ((base % N) * t) % N; } } // Driver code let base = 5; let exp = 100000; let modulo = exponentiation(base, exp); document.write(modulo); document.write(base); // This code is contributed by Gautam goel (gautamgoel962) </script>
Producción :
754573817
-método ario:
En este algoritmo, expandiremos el exponente en base (k>=1), que es de alguna manera similar al método anterior, excepto que no estamos usando recursividad, este método usa comparativamente menos memoria y tiempo.
C++
// C++ program to compute exponential value using (2^k) // -ary method. #include<bits/stdc++.h> using namespace std; #define N 1000000007L; // prime modulo value long exponentiation(long base, long exp) { long t = 1L; while (exp > 0) { // for cases where exponent // is not an even value if (exp % 2 != 0) t = (t * base) % N; base = (base * base) % N; exp /= 2; } return t % N; } // Driver code int main() { long base = 5; long exp = 100000; long modulo = exponentiation(base, exp); cout << (modulo); return 0; } // This code is contributed by Rajput-Ji
Java
// Java program to compute exponential value using (2^k) // -ary method. import java.util.*; import java.lang.*; import java.io.*; class exp_sq { static long N = 1000000007L; // prime modulo value public static void main(String[] args) { long base = 5; long exp = 100000; long modulo = exponentiation(base, exp); System.out.println(modulo); } static long exponentiation(long base, long exp) { long t = 1L; while (exp > 0) { // for cases where exponent // is not an even value if (exp % 2 != 0) t = (t * base) % N; base = (base * base) % N; exp /= 2; } return t % N; } }
Python3
# Python3 program to compute # exponential value # using (2^k) -ary method. # prime modulo value N = 1000000007; def exponentiation(bas, exp): t = 1; while(exp > 0): # for cases where exponent # is not an even value if (exp % 2 != 0): t = (t * bas) % N; bas = (bas * bas) % N; exp = int(exp / 2); return t % N; # Driver Code bas = 5; exp = 100000; modulo = exponentiation(bas,exp); print(modulo); # This code is contributed # by mits
C#
// C# program to compute // exponential value // using (2^k) -ary method. using System; class GFG { // prime modulo value static long N = 1000000007L; static long exponentiation(long bas, long exp) { long t = 1L; while (exp > 0) { // for cases where exponent // is not an even value if (exp % 2 != 0) t = (t * bas) % N; bas = (bas * bas) % N; exp /= 2; } return t % N; } // Driver Code public static void Main () { long bas = 5; long exp = 100000; long modulo = exponentiation(bas, exp); Console.WriteLine(modulo); } } //This code is contributed by ajit
PHP
<?php // PHP program to compute // exponential value // using (2^k) -ary method. // prime modulo value $N = 1000000007; function exponentiation($bas, $exp) { global $N; $t = 1; while ($exp > 0) { // for cases where exponent // is not an even value if ($exp % 2 != 0) $t = ($t * $bas) % $N; $bas = ($bas * $bas) % $N; $exp = (int)$exp / 2; } return $t % $N; } // Driver Code $bas = 5; $exp = 100000; $modulo = exponentiation($bas, $exp); echo ($modulo); // This code is contributed // by ajit ?>
Javascript
// JavaScript program to compute // exponential value // using (2^k) -ary method. // prime modulo value let N = 1000000007n; function exponentiation(bas, exp) { let t = 1n; while(exp > 0n) { // for cases where exponent // is not an even value if (exp % 2n != 0n) t = (t * bas) % N; bas = (bas * bas) % N; exp >>= 1n; } return t % N; } // Driver Code let bas = 5n; let exp = 100000n; let modulo = exponentiation(bas,exp); console.log(Number(modulo)); // This code is contributed // by phasing17
Producción :
754573817
Aplicaciones: además del cálculo rápido de este método, tiene otras ventajas, como que se usa en criptografía, en el cálculo de la exponenciación de arrays , etc.
Publicación traducida automáticamente
Artículo escrito por sanjal_katiyar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA