Menu
In many programming problems (e.g. some Project Euler problems) we are asked to report the answer as the remainder left after dividing the answer by 1,000,000,007.
Why not any other number?
Edit: 2 years later, here's what I know: the number is a big prime, and any answer to such a question is so large that it makes sense to report a remainder instead (as the number may be too large for a native datatype to handle).
443
7 are prime numbers and 1000000007 is the biggest one that fits in 32-bit integer. Since prime numbers are used to calculate hash (by finding the remainder of the division by prime), 1000000007 is good for calculating 32-bit hash.
The reason of taking Mod is to prevent integer overflows. The largest integer data type in C/C++ is unsigned long long int which is of 64 bit and can handle integer from 0 to (2^64 – 1). But in some problems where the growth rate of output is very high, this high range of unsigned long long may be insufficient.
If I say a modulo b is c, it means that the remainder when a is divided by b is c. The modulo operation is represented by the '%' operator in most programming languages (including C/C++/Java/Python). So, 5 % 2 = 1, 17 % 5 = 2, 7 % 9 = 7 and so on.
10^9+7 is a prime number. This means that the "Chinese remainder trick" doesn't apply; if you're trying to work something out modulo a product of two primes, say pq, then you can work it out modulo p and modulo q and use the extended Euclidean algorithm to put the pieces together.
Let me play a telepathist. 1000...7 are prime numbers and 1000000007 is the biggest one that fits in 32-bit integer. Since prime numbers are used to calculate hash (by finding the remainder of the division by prime), 1000000007 is good for calculating 32-bit hash.
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
