Suppose I have two long longs, a and b, that I need to multiply, then get the value mod k for some large k, such that a, b, and k are all in the range of long long but not of int. For simplicity, a, b < k.
Thus the code would be:
long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";
However, since a and b are so large, if you multiply like above, and it overflows and becomes negative, then mod k would be a negative number and incorrect.
How can you ensure that the value mod k is correct?
Edit: As a bonus, how does this work in Java? Is it the same, as expected? Or is BigInteger needed?
Many compilers offer a 128-bit integral type. For example, with
g++
you can make a functionAside: if you can, try to stick to unsigned integer types when you're doing modular arithmetic. The rounding behavior of integer division makes using
%
very awkward when signed values are involved.