You are not logged in. Please login at www.codechef.com to post your questions!

×

Reason for taking modulo

Why is generally modulo 10^9+7 taken in questions? Is there any specific reason for it?

asked 25 May '14, 23:05

castle27's gravatar image

2★castle27
203615
accept rate: 0%


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.

link

answered 26 May '14, 01:26

kcahdog's gravatar image

3★kcahdog
10.0k2854129
accept rate: 14%

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++.

link

answered 25 May '14, 23:20

grayhathacker's gravatar image

5★grayhathacker
3374514
accept rate: 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 ] .

link

answered 25 May '14, 23:25

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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