How to calculate the modulus of the form (a * b)% c?

Question

I want to calculate the multiplication module of two int numbers, where they are almost at the overflow stage ...

here c is also int

+5

Kunal May 06 '11 at 18:54

3 answers

kennytm · Answer 1 · 2011-05-06T19:04:54+0000

(a * b) % c == ((a % c) * (b % c)) % c

Mark b · Answer 2 · 2011-05-06T19:04:56+0000

How about ((a % c) * (b % c)) % c? Depending on your architecture, this may be faster or slower than casting to a larger type.

buc · Answer 3 · 2011-05-06T18:57:24+0000

a c long long, .

((long long)a * (long long)b) % c