I have 3 numbers A, B, and C.
where A = 97830131475, B = 587117 and C = 109546051211. `I wanna get A * B (mod C) without overflow using c++. I used this formula:
unsigned long long x = A % C * B % C; x %= C;
but still getting overflow.
where x = 0. can someone help me!! Thanks in advance. :)
Since C > 232, the product of two numbers might exceed the range of a long long even if you take both numbers mod C first. You could get around this with the following algorithm:
However, it won't help you in this case because you're already getting the correct answer. 97830131475·587117 = 109546051211·524325.