Modulo power for large numbers represented as strings | PHP 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 ; As numbers are very large that is it may contains upto 10 ^ 6 digits . So , we use string .
< ? php $ MOD = 1000000007 ; 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 ; } function powerStrings ( $ sa , $ sb ) { global $ MOD ; $ a = 0 ; $ b = 0 ; for ( $ i = 0 ; $ i < strlen ( $ sa ) ; $ i ++ ) $ a = ( $ a * 10 + ( $ sa [ $ i ] - '0' ) ) % $ MOD ; for ( $ i = 0 ; $ i < strlen ( $ sb ) ; $ i ++ ) $ b = ( $ b * 10 + ( $ sb [ $ i ] - '0' ) ) % ( $ MOD - 1 ) ; return powerLL ( $ a , $ b ) ; } $ sa = "2" ; $ sb = "3" ; echo powerStrings ( $ sa , $ sb ) ; ? >