Finding (a*b)%c where a*b exceeds the range of long long in in C

general
, ,
1

while attempting the question in this link

I could not find an approach for finding (ab)%c where ab exceeds the range of long long in in C.
So, I searched and found this in someone’s solution :
typedef long double LD;
typedef long long LL;

LL big_mult(LL a,LL b,LL mod){

LD ans;
LL c;
a=a%mod;
b=b%mod;
ans=(LD)a*b;
a=a*b;

c=(LL)(ans/mod);
a=a-c*mod;

a=a%mod;
if(a<0)
  a=a+mod;

return a;

}

How can we validate this logic when a*b exceeds the range of long long ?

2

In this question, you need (a/b)%c.

On the other hand, (a*b)%c can be done easily by looking up Russian multiplication.

How to tell if a*b exceeds long long ? See constraints: a,b both are order 10^16 so product is of order 10^32, and long long can take about 10^18-10^19.

Easy to implement in python, but not in c++. Use bigInteger class or python to implement this. Other wise the above code handles the same precision using long double

1 Like