×

# Reason for taking modulo

 0 Why is generally modulo 10^9+7 taken in questions? Is there any specific reason for it? asked 25 May '14, 23:05 2★castle27 20●3●6●15 accept rate: 0%

 1 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. answered 26 May '14, 01:26 3★kcahdog 10.0k●28●54●129 accept rate: 14%
 0 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++. answered 25 May '14, 23:20 337●4●5●14 accept rate: 0%
 0 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 ] . answered 25 May '14, 23:25 4★the65bit 1.1k●10●13●28 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×335

question asked: 25 May '14, 23:05

question was seen: 1,484 times

last updated: 26 May '14, 01:26