Regarding modulo greater than 10^9

general
1

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?

2

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
3

@vijju123 you can use long double as their size is 128bits.

4

Do you mean something like this? It doesn’t appear to be working.

2 Likes
5

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!!

6

@meooow can you tell me why fmod isn’t giving correct answer?

1 Like
7

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

8

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

9

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.

divyanshkumarsblog.wordpress.com