How will you approach a problem if it requires product of 2 numbers modulo {10}^{10}+11 or anything more than {10}^{9}?

Cannot use simple modulo since the product can exceed the range of long long in C++. Any tips/tricks?

How will you approach a problem if it requires product of 2 numbers modulo {10}^{10}+11 or anything more than {10}^{9}?

Cannot use simple modulo since the product can exceed the range of long long in C++. Any tips/tricks?

It can be done in a few ways but the efficiency varies. They are listed at the bottom of this editorial for FOURSQ. The last (and fastest) method can also be found on Wikipedia.

1 Like

(a*b)%mod is equivalent to ((a%mod)*(b%mod))%mod

Hey @vijju123, I had written a blog on this topic. Try taking a look. I have been receiving positive response till now. Dont forget to share it in the community if you find it worth a read.

I remember you sharing the link, but we deleted our answers on that Q since it was from an ongoing contest.(Did a 1 hr fruitless search XD) Thanks for helping!!

I hope its not due to the {10}^{-9} precision error associated with double and float.