How to avoid overflow in modular multiplication ? | To compute ( a * b ) % mod ; res = 0 ; Initialize result ; If b is odd , add ' a ' to result ; Multiply ' a ' with 2 ; Divide b by 2 ; Return result ; Driver Code
def mulmod ( a , b , mod ) : NEW_LINE INDENT a = a % mod ; NEW_LINE while ( b > 0 ) : NEW_LINE INDENT if ( b % 2 == 1 ) : NEW_LINE INDENT res = ( res + a ) % mod ; NEW_LINE DEDENT a = ( a * 2 ) % mod ; NEW_LINE b //= 2 ; NEW_LINE DEDENT return res % mod ; NEW_LINE DEDENT a = 9223372036854775807 ; NEW_LINE b = 9223372036854775807 ; NEW_LINE print ( mulmod ( a , b , 100000000000 ) ) ; NEW_LINE