Why is generally modulo 10^9+7 taken in questions? Is there any specific reason for it?
i think, it’s considered as its value is nearly equal to range(or extremum) of long long int data type and we don’t have any further bigger data type than that in c/c++.
Because it is a prime Number , and its range is near to range of int . @grayhathacker Long Long int have higher range in c++ [ nearly 10^18 ] .
Let us first see why we need a number around 10^9. 10^9 just about less than square root of range of long long. Now say you have a=b=c=10^7 . You want to calculate (a * b * c ) % MOD. You can do SUCH calculations by first doing (a * b) % MOD and then multiplying this with c and then taking MOD again .
If you have very large modulo like 10^15 the a * b = 10 ^ 14. (a * b )% MOD is still 10^14. If you multiply this by c then 10^14 * c = 10^21 which will exceed range of long long and round up to some negative value . If you take MOD now, you will get incorrect result. If you take MOD around 10^9, then (a * b) % MOD will be a number less than MOD. ( i.e. 10^14 % 10^9 is less than 10^9). Now if you multiply it again by c or any number around 10^9, then the result will again be around 10^18 which will fit in range of long long. This is why you must have noticed a lot have questions have 10^9 as limits.
Now comes the question why do we choose a prime number. Prime numbers have a lot of special properties that make calculations simple when calculating modulo in case of division i.e. (a/b ) % MOD. Hence we choose a prime number.
Why 10^9+7. 10^9+7 is very easy to represent. You would rather prefer 10^9 + 7 than something random like 1012383231 or something different everytime. It is for this same reason that some questions use 10^9+9 as MOD since it is also a prime and easy to represent.
1 Like