Dados tres números a, b y m donde 1<=b,m<=10^6 y ‘a’ pueden ser muy grandes y contener hasta 10^6 dígitos. La tarea es encontrar (a^b)%m .
Ejemplos:
Input : a = 3, b = 2, m = 4 Output : 1 Explanation : (3^2)%4 = 9%4 = 1 Input : a = 987584345091051645734583954832576, b = 3, m = 11 Output: 10
Este problema se basa básicamente en la aritmética modular. Podemos escribir (a^b) % m como (a%m) * (a%m) * (a%m) * … (a%m), b veces . A continuación se muestra un algoritmo para resolver este problema:
- Dado que ‘a’ es muy grande, lea ‘a’ como una string.
- Ahora tratamos de reducir ‘a’. Tomamos módulo de ‘a’ por m una vez, es decir; ans = a % m , de esta manera ahora ans=a%m se encuentra entre el rango de enteros de 1 a 10^6, es decir; 1 <= a%m <= 10^6.
- Ahora multiplique ans por b-1 veces y simultáneamente tome la modificación del resultado de la multiplicación intermedia con m porque la multiplicación intermedia de ans puede exceder el rango de enteros y producirá una respuesta incorrecta.
C++
// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
// utility function to calculate a%m
unsigned int aModM(string s, unsigned int mod)
{
unsigned int number = 0;
for (unsigned int i = 0; i < s.length(); i++)
{
// (s[i]-'0') gives the digit value and form
// the number
number = (number*10 + (s[i] - '0'));
number %= mod;
}
return number;
}
// Returns find (a^b) % m
unsigned int ApowBmodM(string &a, unsigned int b,
unsigned int m)
{
// Find a%m
unsigned int ans = aModM(a, m);
unsigned int mul = ans;
// now multiply ans by b-1 times and take
// mod with m
for (unsigned int i=1; i<b; i++)
ans = (ans*mul) % m;
return ans;
}
// Driver program to run the case
int main()
{
string a = "987584345091051645734583954832576";
unsigned int b=3, m=11;
cout << ApowBmodM(a, b, m);
return 0;
}
Java
// Java program to find (a^b) mod m for a large 'a'
public class GFG {
// utility function to calculate a%m
static int aModM(String s, int mod)
{
int number = 0;
for (int i = 0; i < s.length(); i++)
{
// (s[i]-'0') gives the digit
// value and form the number
number = (number * 10 );
int x = Character.getNumericValue(s.charAt(i));
number = number + x;
number %= mod;
}
return number;
}
// Returns find (a^b) % m
static int ApowBmodM(String a, int b, int m)
{
// Find a%m
int ans = aModM(a, m);
int mul = ans;
// now multiply ans by b-1 times
// and take mod with m
for (int i = 1; i < b; i++)
ans = (ans * mul) % m;
return ans;
}
// Driver code
public static void main(String args[])
{
String a = "987584345091051645734583954832576";
int b = 3, m = 11;
System.out.println(ApowBmodM(a, b, m));
}
}
// This code is contributed by Sam007
Python3
# Python program to find (a^b) mod m for a large 'a' def aModM(s, mod): number = 0 # convert string s[i] to integer which gives # the digit value and form the number for i in range(len(s)): number = (number*10 + int(s[i])) number = number % m return number # Returns find (a^b) % m def ApowBmodM(a, b, m): # Find a%m ans = aModM(a, m) mul = ans # now multiply ans by b-1 times and take # mod with m for i in range(1,b): ans = (ans*mul) % m return ans # Driver program to run the case a = "987584345091051645734583954832576" b, m = 3, 11 print (ApowBmodM(a, b, m))
C#
// C# program to find (a^b) mod m
// for a large 'a'
using System;
class GFG {
// utility function to calculate a%m
static int aModM(string s, int mod)
{
int number = 0;
for (int i = 0; i < s.Length; i++)
{
// (s[i]-'0') gives the digit
// value and form the number
number = (number * 10 );
int x = (int)(s[i] - '0');
number = number + x;
number %= mod;
}
return number;
}
// Returns find (a^b) % m
static int ApowBmodM(string a, int b,
int m)
{
// Find a%m
int ans = aModM(a, m);
int mul = ans;
// now multiply ans by b-1 times
// and take mod with m
for (int i = 1; i < b; i++)
ans = (ans * mul) % m;
return ans;
}
// Driver Code
public static void Main()
{
string a = "987584345091051645734583954832576";
int b=3, m=11;
Console.Write(ApowBmodM(a, b, m));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find (a^b)
// mod m for a large 'a'
// utility function to
// calculate a%m
function aModM($s, $mod)
{
$number = 0;
for ($i = 0; $i < strlen($s); $i++)
{
// (s[i]-'0') gives the digit
// value and form the number
$number = ($number * 10 +
($s[$i] - '0'));
$number %= $mod;
}
return $number;
}
// Returns find (a^b) % m
function ApowBmodM($a, $b,$m)
{
// Find a%m
$ans = aModM($a, $m);
$mul = $ans;
// now multiply ans by
// b-1 times and take
// mod with m
for ($i = 1; $i < $b; $i++)
$ans = ($ans * $mul) % $m;
return $ans;
}
// Driver code
$a = "987584345091051645734583954832576";
$b = 3;
$m = 11;
echo ApowBmodM($a, $b, $m);
return 0;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find (a^b) mod m
// for a large 'a'
// Utility function to calculate a%m
function aModM(s, mod)
{
let number = 0;
for(let i = 0; i < s.length; i++)
{
// (s[i]-'0') gives the digit
// value and form the number
number = (number * 10 );
let x = (s[i] - '0');
number = number + x;
number %= mod;
}
return number;
}
// Returns find (a^b) % m
function ApowBmodM(a, b, m)
{
// Find a%m
let ans = aModM(a, m);
let mul = ans;
// Now multiply ans by b-1 times
// and take mod with m
for(let i = 1; i < b; i++)
ans = (ans * mul) % m;
return ans;
}
// Driver Code
let a = "987584345091051645734583954832576";
let b = 3, m = 11;
document.write(ApowBmodM(a, b, m));
// This code is contributed by souravghosh0416
</script>
Producción
10
Complejidad temporal: O(len(a)+b)
Espacio Auxiliar: O(1)
Enfoque eficiente: las multiplicaciones anteriores se pueden reducir a log b mediante el uso de exponenciación modular rápida donde calculamos el resultado mediante la representación binaria del exponente (b) . Si el bit establecido es 1 , multiplicamos el valor actual de la base por el resultado y elevamos al cuadrado el valor de la base para cada llamada recursiva.
Código recursivo:
C++14
// C++ program to find (a^b) mod m for a large 'a', with an
// efficient approach.
#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;
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 * result) % m + m) % m;
}
return (result % m + m) % m;
}
int main()
{
// String input as b is very large
string a = "987584345091051645734583954832576";
// String input as b is very large
ll b = 3;
ll m = 11;
ll remainderA = MOD(a, m);
cout << ModExponent(remainderA, b, m);
return 0;
}
Java
// Java program to find (a^b) mod m for a large 'a', with an
// efficient approach.
public class GFG
{
// Reduce the number B to a small number
// using Fermat Little
static long MOD(String num, long mod)
{
long res = 0;
for (int i = 0; i < num.length(); i++) {
res = (res * 10 + num.charAt(i) - '0') % mod;
}
return res;
}
// Calculate the ModExponent of the given large number
// 'a'
static long ModExponent(long a, long b, long m)
{
long result;
if (a == 0) {
return 0;
}
else if (b == 0) {
return 1;
}
else if (b % 2 != 0) {
result = a % m;
result = result * ModExponent(a, b - 1, m);
}
else {
result = ModExponent(a, b / 2, m);
result = ((result * result) % m + m) % m;
}
return (result % m + m) % m;
}
public static void main(String[] args)
{
// String input as a is very large
String a = "987584345091051645734583954832576";
long b = 3;
long m = 11;
long remainderA = MOD(a, m);
System.out.println(ModExponent(remainderA, b, m));
}
}
// The code is contributed by Gautam goel (gautamgoel962)
Python3
# Python3 program to find (a^b) mod m # for a large 'a' # Utility function to calculate a%m def MOD(s, mod): res = 0 for i in range(len(s)): res = (res * 10 + int(s[i])) % mod return res # Returns find (a^b) % m def ModExponent(a, b, m): if (a == 0): return 0 elif (b == 0): return 1 elif (b % 2 != 0): result = a % m result = result * ModExponent(a, b - 1, m) else: result = ModExponent(a, b / 2, m) result = ((result * result) % m + m) % m return (result % m + m) % m # Driver Code a = "987584345091051645734583954832576" b = 3 m = 11 remainderA = MOD(a, m) print(ModExponent(remainderA, b, m)) # This code is contributed by phasing17
C#
// C# program to find (a^b) mod m for a large 'a', with an
// efficient approach.
using System;
using System.Collections.Generic;
public class GFG {
// Reduce the number B to a small number
// using Fermat Little
static long MOD(string num, long mod)
{
long res = 0;
for (int i = 0; i < num.Length; i++) {
res = (res * 10 + num[i] - '0') % mod;
}
return res;
}
// Calculate the ModExponent of the given large number
// 'a'
static long ModExponent(long a, long b, long m)
{
long result;
if (a == 0) {
return 0;
}
else if (b == 0) {
return 1;
}
else if (b % 2 != 0) {
result = a % m;
result = result * ModExponent(a, b - 1, m);
}
else {
result = ModExponent(a, b / 2, m);
result = ((result * result) % m + m) % m;
}
return (result % m + m) % m;
}
// Driver Code
public static void Main(string[] args)
{
// String input as a is very large
string a = "987584345091051645734583954832576";
long b = 3;
long m = 11;
// Function Call
long remainderA = MOD(a, m);
Console.WriteLine(ModExponent(remainderA, b, m));
}
}
// The code is contributed by phasing17
Javascript
<script>
// JavaScript program to find (a^b) mod m
// for a large 'a'
// Utility function to calculate a%m
function MOD(s, mod)
{
var res = 0;
for (var i = 0; i < s.length; i++) {
res = (res * 10 + (s[i] - '0')) % mod;
}
return res;
}
// Returns find (a^b) % m
function ModExponent(a, b, m)
{
var result;
if (a == 0) {
return 0;
}
else if (b == 0) {
return 1;
}
else if (b % 2 != 0) {
result = a % m;
result = result * ModExponent(a, b - 1, m);
}
else {
result = ModExponent(a, b / 2, m);
result = ((result * result) % m + m) % m;
}
return (result % m + m) % m;
}
// Driver Code
let a = "987584345091051645734583954832576";
let b = 3, m = 11;
var remainderA = MOD(a, m);
document.write(ModExponent(remainderA, b, m));
// This code is contributed by shinjanpatra.
</script>
Producción
10
Complejidad temporal: O(len(a)+ log b)
Espacio Auxiliar: O(log b)
Código iterativo eficiente en el espacio:
C++14
// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// utility function to calculate a%m and b%m
ll aModM(string s, ll mod)
{
ll number = 0;
for (ll i = 0; i < s.length(); i++)
{
// (s[i]-'0') gives the digit value and form
// the number
number = (number*10 + (s[i] - '0'));
number %= mod;
}
return number;
}
// Returns find (a^b) % m
ll ApowBmodM(ll x, ll y,ll m)
{
ll res=1;
while(y)
{
if(y&1)
res=(res*x)%m;
y=y>>1;
x=((x*x)%m+m)%m;
}
return (res%m+m)%m;
}
// Driver program to run the case
int main()
{
string a = "987584345091051645734583954832576";
ll b=3;
ll m=11;
// Find a%m
ll x=aModM(a,m);
cout << ApowBmodM(x,b,m);
return 0;
}
Javascript
// JavaScript program to find (a^b) mod m for a large 'a'
// utility function to calculate a%m and b%m
function aModM(s, mod)
{
let number = 0;
for (var i = 0; i < s.length; i++) {
// parseInt(s[i]) gives the digit value and form
// the number
number = (number * 10 + parseInt(s[i]));
number %= mod;
}
return number;
}
// Returns find (a^b) % m
function ApowBmodM(x, y, m)
{
let res = 1;
while (y) {
if (y & 1)
res = (res * x) % m;
y = y >> 1;
x = ((x * x) % m + m) % m;
}
return (res % m + m) % m;
}
// Driver program to run the case
let a = "987584345091051645734583954832576";
let b = 3;
let m = 11;
// Find a%m
let x = aModM(a, m);
console.log(ApowBmodM(x, b, m));
// This code is contributed by phasing17
Python3
# Python3 program to find (a^b) mod m for a large 'a' # utility function to calculate a%m and b%m def aModM(s, mod): number = 0; for i in range(len(s)): # int(s[i]) gives the digit value and form # the number number = (number * 10 + int(s[i])); number %= mod; return number; # Returns find (a^b) % m def ApowBmodM(x, y, m): res = 1; while (y > 0): if (y & 1): res = (res * x) % m; y = y >> 1; x = ((x * x) % m + m) % m; return (res % m + m) % m; # Driver program to run the case a = "987584345091051645734583954832576"; b = 3; m = 11; # Find a%m x = aModM(a, m); print(ApowBmodM(x, b, m)); # This code is contributed by phasing17
Producción
10
Complejidad temporal: O(len(a)+ log b)
Espacio Auxiliar: O(1)
Caso: Cuando tanto ‘a’ como ‘b’ son muy grandes.
También podemos implementar el mismo enfoque si tanto ‘a’ como ‘b’ fueran muy grandes. En ese caso, primero lo habríamos modificado con m usando nuestra función aModM . Luego páselo a la función recursiva o iterativa ApowBmodM anterior para obtener el resultado requerido.
Código recursivo:
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;
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()
{
// String input as b is very large
string a = "987584345091051645734583954832576";
// String input as b is very large
string b = "467687655456765756453454365476765";
ll m = 1000000007;
ll remainderA = MOD(a,m);
ll remainderB = MOD(b,m);
cout << ModExponent(remainderA, remainderB, m);
return 0;
}
Producción
546081867
Complejidad del tiempo: O(len(a)+len(b)+log b)
Espacio Auxiliar: O(log b)
Código iterativo eficiente en el espacio:
C++14
// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// utility function to calculate a%m and b%m
ll aModM(string s, ll mod)
{
ll number = 0;
for (ll i = 0; i < s.length(); i++)
{
// (s[i]-'0') gives the digit value and form
// the number
number = (number*10 + (s[i] - '0'));
number %= mod;
}
return number;
}
// Returns find (a^b) % m
ll ApowBmodM(string &a, string& b,ll m)
{
ll res=1;
// Find a%m
ll x = aModM(a,m);
// Find b%m
ll y = aModM(b,m);
while(y)
{
if(y&1)
res=(res*x)%m;
y=y>>1;
x=((x%m)*(x%m))%m;
}
return (res%m+m)%m;
}
// Driver program to run the case
int main()
{
string a = "987584345091051645734583954832576";
string b="467687655456765756453454365476765";
ll m=1000000007;
cout << ApowBmodM(a,b,m);
return 0;
}
Producción
546081867
Complejidad del tiempo: O(len(a)+len(b)+ log b)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) y mejorado por Prophet1999 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA