Dados tres números a , b y m donde 1<=a, m<=10^6 . Dada una ‘b’ muy grande que contiene hasta 10^6 dígitos y m es un número primo, la tarea es encontrar (a^b)%m .
Ejemplos:
Entrada: a = 2, b = 3, m = 17
Salida: 8
2 ^ 3 % 17 = 8
Entrada: a = 3, b = 100000000000000000000000000, m = 1000000007
Salida: 835987331
Enfoque iterativo: de acuerdo con el pequeño teorema de Fermat y la exponenciación modular,
a^(p-1) mod p = 1, When p is prime.
A partir de esto, a partir del problema, M es primo, exprese A^B mod M de la siguiente manera:
A^B mod M = ( A^(M-1) * A^(M-1) *.......* A^(M-1) * A^(x) ) mod M
Donde x es B mod M-1 y A ^ (M-1) continúa B/(M-1) veces
Ahora, del pequeño teorema de Fermat,
A ^ (M-1) mod M = 1.
Por eso,
A^B mod M = ( 1 * 1 * ....... * 1 * A^(x) ) mod M
Por lo tanto , mod B con M-1 para reducir el número a uno más pequeño y luego usar el método power() para calcular (a^b)%m .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// (a^b)%m for b very large.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function to find power
ll power(ll x, ll y, ll p)
{
ll res = 1; // Initialize result
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x
// with the result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Driver Code
int main()
{
ll a = 3;
// String input as b is very large
string b = "100000000000000000000000000";
ll remainderB = 0;
ll MOD = 1000000007;
// Reduce the number B to a small number
// using Fermat Little
for (int i = 0; i < b.length(); i++)
remainderB = (remainderB * 10 +
b[i] - '0') % (MOD - 1);
cout << power(a, remainderB, MOD) << endl;
return 0;
}
Java
// Java program to find
// (a^b)%m for b very large.
import java.io.*;
class GFG
{
// Function to find power
static long power(long x,
long y, long p)
{
long res = 1; // Initialize result
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with the result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Driver Code
public static void main (String[] args)
{
long a = 3;
// String input as
// b is very large
String b = "100000000000000000000000000";
long remainderB = 0;
long MOD = 1000000007;
// Reduce the number B to a small
// number using Fermat Little
for (int i = 0; i < b.length(); i++)
remainderB = (remainderB * 10 +
b.charAt(i) - '0') %
(MOD - 1);
System.out.println(power(a, remainderB, MOD));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to find # (a^b)%m for b very large. # Function to find power def power(x, y, p): res = 1 # Initialize result # Update x if it is # more than or equal to p x = x % p while (y > 0): # If y is odd, multiply # x with the result if (y & 1): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res # Driver Code a = 3 # String input as b # is very large b = "100000000000000000000000000" remainderB = 0 MOD = 1000000007 # Reduce the number B # to a small number # using Fermat Little for i in range(len(b)): remainderB = ((remainderB * 10 + ord(b[i]) - 48) % (MOD - 1)) print(power(a, remainderB, MOD)) # This code is contributed by mits
C#
// C# program to find
// (a^b)%m for b very large.
using System;
class GFG
{
// Function to find power
static long power(long x,
long y, long p)
{
// Initialize result
long res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with the result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Driver Code
public static void Main ()
{
long a = 3;
// String input as
// b is very large
string b = "100000000000000000000000000";
long remainderB = 0;
long MOD = 1000000007;
// Reduce the number B to
// a small number using
// Fermat Little
for (int i = 0; i < b.Length; i++)
remainderB = (remainderB * 10 +
b[i] - '0') %
(MOD - 1);
Console.WriteLine(power(a, remainderB, MOD));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find
// (a^b)%m for b very large.
// Function to find power
function power($x, $y, $p)
{
$res = 1; // Initialize result
// Update x if it is
// more than or equal to p
$x = $x % $p;
while ($y > 0)
{
// If y is odd, multiply
// x with the result
if ($y & 1)
$res = ($res * $x) % $p;
// y must be even now
$y = $y >> 1; // y = y/2
$x = ($x * $x) % $p;
}
return $res;
}
// Driver Code
$a = 3;
// String input as b
// is very large
$b = "100000000000000000000000000";
$remainderB = 0;
$MOD = 1000000007;
// Reduce the number B
// to a small number
// using Fermat Little
for ($i = 0; $i < strlen($b); $i++)
$remainderB = ($remainderB * 10 +
$b[$i] - '0') %
($MOD - 1);
echo power($a, $remainderB, $MOD);
// This code is contributed by mits
?>
835987331
Complejidad de tiempo: O(len(b)+log b)
Espacio Auxiliar: O(1)
Enfoque recursivo: es igual a la implementación anterior, excepto por el hecho de que tenemos que pasar el resultado de cada subproblema a la pila de recurrencia de retroceso.
C++14
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Reduce the number B to a small number
// using Fermat Little
ll MOD(string num,int mod)
{
ll res=0;
for(int i=0;i<num.length();i++)
res=(res*10+num[i]-'0')%(mod-1);
return res;
}
ll ModExponent(ll a,ll b,ll m)
{
ll result;
if(a==0)
return 0;
else if(b==0)
return 1;
else if(b&1)
{
result=a%m;
result=result*ModExponent(a,b-1,m);
}
else{
result=ModExponent(a,b/2,m);
result=((result%m)*(result%m))%m;
}
return (result%m+m)%m;
}
int main()
{
ll a = 3;
// String input as b is very large
string b = "100000000000000000000000000";
ll m = 1000000007;
ll remainderB = MOD(b,m);
cout << ModExponent(a, remainderB, m) << endl;
return 0;
}
835987331
Complejidad de tiempo: O(len(b)+log b)
Espacio Auxiliar: O(log b)
Publicación traducida automáticamente
Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA