Modulo power for large numbers represented as strings
Given two numbers sa and sb represented as strings, find ab % MOD where MOD is 1e9 + 7. The numbers a and b can contain upto 106 digits.
Examples:
Input : sa = 2, sb = 3
Output : 8
Input : sa = 10000000000000000000000000000000000000000000
sb = 10000000000000000000000000000000000000000000
Output : 494234546
As a and b very large (may contain upto 10^6 digits each). So what we can do, we apply Fermat’s little theorem and property of modulo to reduce a and b.
Reduce a:
As we know,
(ab) % MOD = ((a % MOD)b) % MOD
Reduce b:
How to reduce b, We have already discuss in Find (a^b)%m where ‘b’ is very large
Now finally we have both a and b are in range of 1<=a, b<=10^9+7. Hence we can now use our modular exponentiation to calculate required answer.
C++
// CPP program to find (a^b) % MOD where a and // b may be very large and represented as strings. #include <bits/stdc++.h> using namespace std; #define ll long long int const ll MOD = 1e9 + 7; // Returns modulo exponentiation for two numbers // represented as long long int. It is used by // powerStrings(). Its complexity is log(n) ll powerLL(ll x, ll n) { ll result = 1; while (n) { if (n & 1) result = result * x % MOD; n = n / 2; x = x * x % MOD; } return result; } // Returns modulo exponentiation for two numbers // represented as strings. It is used by // powerStrings() ll powerStrings(string sa, string sb) { // We convert strings to number ll a = 0, b = 0; // calculating a % MOD for ( int i = 0; i < sa.length(); i++) a = (a * 10 + (sa[i] - '0' )) % MOD; // calculating b % (MOD - 1) for ( int i = 0; i < sb.length(); i++) b = (b * 10 + (sb[i] - '0' )) % (MOD - 1); // Now a and b are long long int. We // calculate a^b using modulo exponentiation return powerLL(a, b); } int main() { // As numbers are very large // that is it may contains upto // 10^6 digits. So, we use string. string sa = "2" , sb = "3" ; cout << powerStrings(sa, sb) << endl; return 0; } |
Java
// Java program to find (a^b) % MOD // where a and b may be very large // and represented as strings. import java.util.*; class GFG { static long MOD = ( long ) (1e9 + 7 ); // Returns modulo exponentiation for two numbers // represented as long long int. It is used by // powerStrings(). Its complexity is log(n) static long powerLL( long x, long n) { long result = 1 ; while (n > 0 ) { if (n % 2 == 1 ) { result = result * x % MOD; } n = n / 2 ; x = x * x % MOD; } return result; } // Returns modulo exponentiation for // two numbers represented as strings. // It is used by powerStrings() static long powerStrings(String sa, String sb) { // We convert strings to number long a = 0 , b = 0 ; // calculating a % MOD for ( int i = 0 ; i < sa.length(); i++) { a = (a * 10 + (sa.charAt(i) - '0' )) % MOD; } // calculating b % (MOD - 1) for ( int i = 0 ; i < sb.length(); i++) { b = (b * 10 + (sb.charAt(i) - '0' )) % (MOD - 1 ); } // Now a and b are long long int. We // calculate a^b using modulo exponentiation return powerLL(a, b); } // Driver code public static void main(String[] args) { // As numbers are very large // that is it may contains upto // 10^6 digits. So, we use string. String sa = "2" , sb = "3" ; System.out.println(powerStrings(sa, sb)); } } // This code is contributed by Rajput-JI |
Python3
# Python3 program to find (a^b) % MOD # where a and b may be very large # and represented as strings. MOD = 1000000007 ; # Returns modulo exponentiation # for two numbers represented as # long long int. It is used by # powerStrings(). Its complexity # is log(n) def powerLL(x, n): result = 1 ; while (n): if (n & 1 ): result = result * x % MOD; n = int (n / 2 ); x = x * x % MOD; return result; # Returns modulo exponentiation # for two numbers represented as # strings. It is used by powerStrings() def powerStrings(sa, sb): # We convert strings to number a = 0 ; b = 0 ; # calculating a % MOD for i in range ( len (sa)): a = (a * 10 + ( ord (sa[i]) - ord ( '0' ))) % MOD; # calculating b % (MOD - 1) for i in range ( len (sb)): b = (b * 10 + ( ord (sb[i]) - ord ( '0' ))) % (MOD - 1 ); # Now a and b are long long int. # We calculate a^b using modulo # exponentiation return powerLL(a, b); # Driver code # As numbers are very large # that is it may contains upto # 10^6 digits. So, we use string. sa = "2" ; sb = "3" ; print (powerStrings(sa, sb)); # This code is contributed by mits |
C#
// C# program to find (a^b) % MOD where a and b // may be very large and represented as strings. using System; class GFG { static long MOD = ( long ) (1e9 + 7); // Returns modulo exponentiation for two numbers // represented as long long int. It is used by // powerStrings(). Its complexity is log(n) static long powerLL( long x, long n) { long result = 1; while (n > 0) { if (n % 2 == 1) { result = result * x % MOD; } n = n / 2; x = x * x % MOD; } return result; } // Returns modulo exponentiation for // two numbers represented as strings. // It is used by powerStrings() static long powerStrings(String sa, String sb) { // We convert strings to number long a = 0, b = 0; // calculating a % MOD for ( int i = 0; i < sa.Length; i++) { a = (a * 10 + (sa[i] - '0' )) % MOD; } // calculating b % (MOD - 1) for ( int i = 0; i < sb.Length; i++) { b = (b * 10 + (sb[i] - '0' )) % (MOD - 1); } // Now a and b are long long int. We // calculate a^b using modulo exponentiation return powerLL(a, b); } // Driver code public static void Main(String[] args) { // As numbers are very large // that is it may contains upto // 10^6 digits. So, we use string. String sa = "2" , sb = "3" ; Console.WriteLine(powerStrings(sa, sb)); } } // This code is contributed by 29AjayKumar |
PHP
<?php // PHP program to find (a^b) % MOD // where a and b may be very large // and represented as strings. $MOD = 1000000007; // Returns modulo exponentiation // for two numbers represented as // long long int. It is used by // powerStrings(). Its complexity // is log(n) function powerLL( $x , $n ) { global $MOD ; $result = 1; while ( $n ) { if ( $n & 1) $result = $result * $x % $MOD ; $n = (int) $n / 2; $x = $x * $x % $MOD ; } return $result ; } // Returns modulo exponentiation // for two numbers represented as // strings. It is used by powerStrings() function powerStrings( $sa , $sb ) { global $MOD ; // We convert strings to number $a = 0; $b = 0; // calculating a % MOD for ( $i = 0; $i < strlen ( $sa ); $i ++) $a = ( $a * 10 + ( $sa [ $i ] - '0' )) % $MOD ; // calculating b % (MOD - 1) for ( $i = 0; $i < strlen ( $sb ); $i ++) $b = ( $b * 10 + ( $sb [ $i ] - '0' )) % ( $MOD - 1); // Now a and b are long long int. // We calculate a^b using modulo // exponentiation return powerLL( $a , $b ); } // Driver code // As numbers are very large // that is it may contains upto // 10^6 digits. So, we use string. $sa = "2" ; $sb = "3" ; echo powerStrings( $sa , $sb ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find (a^b) % MOD where a and b // may be very large and represented as strings. let MOD = (1e9 + 7); // Returns modulo exponentiation for two numbers // represented as long long let. It is used by // powerStrings(). Its complexity is log(n) function powerLL(x, n) { let result = 1; while (n > 0) { if (n % 2 == 1) { result = result * x % MOD; } n = Math.floor(n / 2); x = x * x % MOD; } return result; } // Returns modulo exponentiation for // two numbers represented as strings. // It is used by powerStrings() function powerStrings(sa, sb) { // We convert strings to number let a = 0, b = 0; // calculating a % MOD for (let i = 0; i < sa.length; i++) { a = (a * 10 + (sa[i] - '0' )) % MOD; } // calculating b % (MOD - 1) for (let i = 0; i < sb.length; i++) { b = (b * 10 + (sb[i] - '0' )) % (MOD - 1); } // Now a and b are long long let. We // calculate a^b using modulo exponentiation return powerLL(a, b); } // Driver Code // As numbers are very large // that is it may contains upto // 10^6 digits. So, we use string. let sa = "2" , sb = "3" ; document.write(powerStrings(sa, sb)); </script> |
8
Time Complexity: O(n+m) where n and m are lengths of strings sa and sb.
Auxiliary Space: O(1)