Modulo power for large numbers represented as strings | CPP program to find ( a ^ b ) % MOD where a and b may be very large and represented as strings . ; Returns modulo exponentiation for two numbers represented as long long int . It is used by powerStrings ( ) . Its complexity is log ( n ) ; Returns modulo exponentiation for two numbers represented as strings . It is used by powerStrings ( ) ; We convert strings to number ; calculating a % MOD ; calculating b % ( MOD - 1 ) ; Now a and b are long long int . We calculate a ^ b using modulo exponentiation ; Driver code ; As numbers are very large that is it may contains upto 10 ^ 6 digits . So , we use string .
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE const ll MOD = 1e9 + 7 ; 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 ; } ll powerStrings ( string sa , string sb ) { ll a = 0 , b = 0 ; for ( int i = 0 ; i < sa . length ( ) ; i ++ ) a = ( a * 10 + ( sa [ i ] - '0' ) ) % MOD ; for ( int i = 0 ; i < sb . length ( ) ; i ++ ) b = ( b * 10 + ( sb [ i ] - '0' ) ) % ( MOD - 1 ) ; return powerLL ( a , b ) ; } int main ( ) { string sa = "2" , sb = "3" ; cout << powerStrings ( sa , sb ) << endl ; return 0 ; }