How to avoid overflow in modular multiplication ? | C ++ program for modular multiplication without any overflow ; To compute ( a * b ) % mod ; ll res = 0 ; Initialize result ; If b is odd , add ' a ' to result ; Multiply ' a ' with 2 ; Divide b by 2 ; Return result ; Driver program
#include <iostream> NEW_LINE using namespace std ; typedef long long int ll ; ll mulmod ( ll a , ll b , ll mod ) { a = a % mod ; while ( b > 0 ) { if ( b % 2 == 1 ) res = ( res + a ) % mod ; a = ( a * 2 ) % mod ; b /= 2 ; } return res % mod ; } int main ( ) { ll a = 9223372036854775807 , b = 9223372036854775807 ; cout << mulmod ( a , b , 100000000000 ) ; return 0 ; }