Find (a^b)%m where ‘a’ ‘b’ and ‘c’ is very large number
Given three numbers a, b, and m where10^9 ≤ a, b ≤ 10^9. Given very large ‘m’ containing 10^18+7 and m is a prime number, the task is to find (a ^ b) % m.
Example:
Input: a = “5541548454152524154”, b = “946646454116451”, M = 1e18+7
Output: 588288874981883904Input: a = “5454656454154”, b = “5646546546465446”, M = 1e18+7
Output: 654515516062826496
Approach: To solve the problem follow the below observations:
In this type of case, we can face a problem with using Binary Exponentiation. As M is 1018+7 then in some cases we can not store a value greater than INT_MAX.
According to Fermat’s little theorem and Modular Exponentiation:
- a ^ (p – 1) mod p = 1, When p is prime.
From this, as of the problem, M is prime, express A ^ B mod M as follows:
A^B mod M = ( A^(M-1) * A^(M-1) *…….* A^(M-1) * A^(x) ) mod M
- Where x is B mod M – 1 and A ^ (M – 1) continues B/(M-1) times
Now, from Fermat’s Little Theorem, A ^ (M-1) mod M = 1.Hence,
A^B mod M = ( 1 * 1 * ……. * 1 * A^(x) ) mod M
- Hence mod B with M-1 to reduce the number to a smaller one and then use the power() method to compute (a ^ b)%m.
We can write binary exponential code considering a ≤ 1018 and b ≤ 1018. if a > 1018 or b > 1018 we can go through the method mentioned in 2 and 3 no article and then apply this for Big m.
Below is the implementation for the above approach:
C++
// C++ Implementation to write binary // exponenetial code #include <iostream> using namespace std; const long long M = 1e9 + 7; // Function for binary Exponenetial code long long BinExp( long long a, long long b) { long long ans = 1; while (b > 0) { if (b & 1) { ans = (ans * a) % M; } a = (a * a) % M; b >>= 1; } return ans; } // Driver code int main() { // Function call cout << BinExp(2, 10); return 0; } |
Java
// Java code for the above approach class GFG { static final long M = 1000000007 ; // Function for binary Exponenetial code public static long BinExp( long a, long b) { long ans = 1 ; while (b > 0 ) { // Checking bit is set or not if ((b & 1 ) == 1 ) { // multiply a to ans if number is odd ans = (ans * a) % M; } a = (a * a) % M; // Right shift to divide the number b >>= 1 ; } return ans; } // Driver code public static void main(String[] args) { System.out.println(BinExp( 2 , 10 )); } } // This code is contributed by ragul21 |
C#
using System; public class Program { const long M = 1000000007; // Function for binary Exponenetial code public static long BinExp( long a, long b) { long ans = 1; while (b > 0) { // Checking bit is set or not if ((b & 1) == 1) { // multiply a to ans if number is odd ans = (ans * a) % M; } a = (a * a) % M; // Right shift to divide the number b >>= 1; } return ans; } // Driver code public static void Main() { Console.WriteLine(BinExp(2, 10)); } } |
Javascript
function GFG(a, b) { const M = 1e9 + 7; // The Modulus value let ans = 1; while (b > 0) { if (b & 1) { ans = (ans * a) % M; } a = (a * a) % M; b >>= 1; } return ans; } // Driver code function main() { // Function call const result = GFG(2, 10); console.log(result); } main(); |
Python3
# variable for mod function M = 10 * * 9 + 7 # Function for binary Exponenetial code def BinExp(a, b): ans = 1 # making a^b while b > 0 : # If b is odd multiply a to ans if b & 1 : ans = (ans * a) % M a = (a * a) % M # left shit with 1 operation divide the number by 2 b >> = 1 return ans print (BinExp( 2 , 10 )) |
1024
It will run fine when M will be ordered 107. But when M is the order of 1018 then we will face a problem. So, there are 2 following cases:
- When (ans * a ) is occurring then if a is in order of 10^18 and ans is also in the same order then an overflow can take place which causes a negative answer.
- When (a * a ) is occurring then if a is in order of 10^18 then an overflow can take place as 10^18 * 10^18 = 10^36 which causes a negative answer.
To tackle this we can follow the binary multiplication rule:
In this case we can use (a + a + a + a…) in the position of a * a . In words we can say that instead of doing direct multiplication we can use multiplication by cosecutive addition and taking modulous . And in this case We can get At most 2 * 10^18 which is in range.
Binary Multiplication Process:
a + a ≤ 2 * 10^18
(a + a) % M ≤ 10^18(a +a + a) ≤ 2 * 10^18
(a + a + a) % M ≤ 10^18 … So on.
We can do the process following Binary exponentiation. In Binary multiplication when the bit of the number is set then we will add (ans + a) in place of (ans * a) and we will add (a + a) in place of (a * a) so that no overflow occurred.
C++
#include <iostream> using namespace std; const int M = 1000000007; // Modulo value // Function to perform binary multiplication (a * b) % M int BinMul( int a, int b) { int ans = 1; while (b > 0) { if (b & 1) { // When the least significant bit of b is set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1; // Right shift the number by 1 } return ans; } // Driver Method int main() { int a = 10; int b = 20; int result = BinMul(a, b); cout << "Result: " << result << endl; return 0; } |
Java
public class Main { static final int M = 1000000007 ; // Modulo value // Function to perform binary multiplication (a * b) % M static int binMul( int a, int b) { int ans = 1 ; while (b > 0 ) { if ((b & 1 ) == 1 ) { // When the least significant bit of b is set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1 ; // Right shift the number by 1 } return ans; } // Driver Method public static void main(String[] args) { int a = 10 ; int b = 20 ; int result = binMul(a, b); System.out.println( "Result: " + result); } } |
Python
# Function to perform binary multiplication (a * b) % M def bin_mul(a, b): ans = 1 M = 1000000007 # Modulo value while b > 0 : if b & 1 : # When the least significant bit of b is set ans = (ans + a) % M # Doing normal addition a = (a + a) % M b >> = 1 # Right shift the number by 1 return ans # Driver Method if __name__ = = "__main__" : a = 10 b = 20 result = bin_mul(a, b) print ( "Result:" , result) |
C#
using System; class MainClass { const long M = 1000000007; // Modulo value // Function to perform binary multiplication (a * b) % M static long BinMul( long a, long b) { long ans = 1; while (b > 0) { if ((b & 1) == 1) { // When the least significant bit of b is // set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1; // Right shift the number by 1 } return ans; } // Driver Method public static void Main( string [] args) { long a = 10; long b = 20; long result = BinMul(a, b); Console.WriteLine( "Result: " + result); } } |
Javascript
// Javascript program for the above approach const M = 1000000007; // Modulo value // Function to perform binary multiplication (a * b) % M function BinMul(a, b) { let ans = 1; while (b > 0) { if (b & 1) { // When the least significant bit of b is set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1; // Right shift the number by 1 } return ans; } // Driver Method let a = 10; let b = 20; let result = BinMul(a, b); console.log( "Result: " + result); // This code is contributed by Susobhan Akhuli |
This function will help us to find (A * B) when A and B are ordered of 10^18. So in Binary Exponentiation in place of multiplication, we will use this function to avoid overflow. Combining all the above approaches we can get a proper approach.
Below is the implementation of the Above Approach:
C++
// C++ Implementation #include <iostream> using namespace std; const long long M = 1e18 + 7; // Calculate Mod of A long long MODA(string num) { long long res = 0; for ( long long int i = 0; i < num.length(); i++) res = (res * 10 + num[i] - '0' ) % M; return res; } // Calculate Mod of B long long MODB(string b) { long long res = 0; for ( int i = 0; i < b.length(); i++) res = (res * 10 + b[i] - '0' ) % (M - 1); return res; } // Binary Multiplication Cade long long BinMul( long long a, long long b) { long long ans = 0; while (b > 0) { if (b & 1) { // When the bit is set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1; // right shift the number by 1 } return ans; } // Binary Exponentitation Code long long BinExp( long long a, long long b) { long long ans = 1; while (b > 0) { if (b & 1) { ans = BinMul(a, ans); } a = BinMul(a, a); b >>= 1; } return ans; } // Driver code int main() { string a = "5541548454152524154" , b = "946646454116451" ; long long aa = MODA(a); long long bb = MODB(b); // Function call // Taking a = 10^16 + 7 and b = 100 cout << BinExp(aa, bb); return 0; } |
Java
import java.math.BigInteger; public class Main { static final long M = 1000000000000000007L; // Calculate Mod of A static long MODA(String num) { long res = 0 ; for ( int i = 0 ; i < num.length(); i++) { res = (res * 10 + num.charAt(i) - '0' ) % M; } return res; } // Calculate Mod of B static long MODB(String b) { long res = 0 ; for ( int i = 0 ; i < b.length(); i++) { res = (res * 10 + b.charAt(i) - '0' ) % (M - 1 ); } return res; } // Binary Multiplication Code static long BinMul( long a, long b) { long ans = 0 ; while (b > 0 ) { if ((b & 1 ) == 1 ) { // When the bit is set ans = (ans + a) % M; // Doing normal addition } a = (a + a) % M; b >>= 1 ; // right shift the number by 1 } return ans; } // Binary Exponentiation Code static long BinExp( long a, long b) { long ans = 1 ; while (b > 0 ) { if ((b & 1 ) == 1 ) { ans = BinMul(a, ans); } a = BinMul(a, a); b >>= 1 ; } return ans; } // Driver code public static void main(String[] args) { String a = "5541548454152524154" ; String b = "946646454116451" ; long aa = MODA(a); long bb = MODB(b); // Function call // Taking a = 10^16 + 7 and b = 100 System.out.println(BinExp(aa, bb)); } } |
C#
using System; class Program { const long M = 1000000000000000007; // 10^18 + 7 // Calculate Mod of A static long MODA( string num) { long res = 0; foreach ( char digit in num) { res = (res * 10 + (digit - '0' )) % M; } return res; } // Calculate Mod of B static long MODB( string b) { long res = 0; foreach ( char digit in b) { res = (res * 10 + (digit - '0' )) % (M - 1); } return res; } // Binary Multiplication Code static long BinMul( long a, long b) { long ans = 0; while (b > 0) { if ((b & 1) != 0) { // When the bit is set ans = (ans + a) % M; } a = (a + a) % M; b >>= 1; // right shift the number by 1 } return ans; } // Binary Exponentiation Code static long BinExp( long a, long b) { long ans = 1; while (b > 0) { if ((b & 1) != 0) { ans = BinMul(a, ans); } a = BinMul(a, a); b >>= 1; } return ans; } // Driver code static void Main() { string a = "5541548454152524154" ; string b = "946646454116451" ; long aa = MODA(a); long bb = MODB(b); // Function call // Taking a = 10^16 + 7 and b = 100 Console.WriteLine(BinExp(aa, bb)); } } |
Javascript
const M = BigInt(10 ** 18 + 7); // Calculate Mod of A function MODA(num) { let res = BigInt(0); for (let i = 0; i < num.length; i++) { res = (res * BigInt(10) + BigInt(num[i]) - BigInt( '0' )) % M; } return res; } // Calculate Mod of B function MODB(b) { let res = BigInt(0); for (let i = 0; i < b.length; i++) { res = (res * BigInt(10) + BigInt(b[i]) - BigInt( '0' )) % (M - BigInt(1)); } return res; } // Binary Multiplication Code function BinMul(a, b) { let ans = BigInt(0); while (b > 0n) { if (b & 1n) { ans = (ans + a) % M; } a = (a + a) % M; b >>= 1n; } return ans; } // Binary Exponentiation Code function BinExp(a, b) { let ans = BigInt(1); while (b > 0n) { if (b & 1n) { ans = BinMul(a, ans); } a = BinMul(a, a); b >>= 1n; } return ans; } // Driver code const a = "5541548454152524154" ; const b = "946646454116451" ; const aa = MODA(a); const bb = MODB(b); // Function call console.log(BinExp(aa, bb).toString()); |
Python3
# Calculate Mod of A def moda(num): res = 0 for i in range ( len (num)): res = (res * 10 + int (num[i])) % M return res # Calculate Mod of B def modb(b): res = 0 for i in range ( len (b)): res = (res * 10 + int (b[i])) % (M - 1 ) return res # Binary Multiplication Code def binmul(a, b): ans = 0 while b > 0 : if b & 1 : # When the bit is set ans = (ans + a) % M # Doing normal addition a = (a + a) % M b >> = 1 # Right shift the number by 1 return ans # Binary Exponentiation Code def binexp(a, b): ans = 1 while b > 0 : if b & 1 : ans = binmul(a, ans) a = binmul(a, a) b >> = 1 return ans # Main function if __name__ = = "__main__" : M = 10 * * 18 + 7 # Modulus a = "5541548454152524154" b = "946646454116451" aa = moda(a) bb = modb(b) # Function call # Taking a = 10^16 + 7 and b = 100 print (binexp(aa, bb)) |
588288874981883904
Time Complexity: O((log(N))2)
Auxiliary Space: O(1)