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

×

Modulo 10^9 +7

2
1

Why are we ask to take modulo 10^9 + 7 (1000000007) in many problems? What is the arithmetic logic behind it can anyone clear it out?

Thanks!

asked 08 May '14, 19:15

tech_boy's gravatar image

3★tech_boy
1.2k41931
accept rate: 7%


Quoting Anton Lunyov,

" It is the first 10-digital prime number. In some of such problems to compute the result modular inverses are needed and it helps very much that this number is prime. Also this number should be large enough since otherwise modular inverses technique may fail in some situations.

In fact any prime number less then 2^30 will be fine in order to prevent possible overflows. But this one can be easily written as 10^9+7.

This reasoning almost uniquely determined this number :) "

Source: What's significant about the number choice 1000000007?

link

answered 08 May '14, 19:52

wittyceaser's gravatar image

3★wittyceaser
3.4k194374
accept rate: 15%

The above operation guarentees that the result after operation fits in integer data type i.e it makes sure that there is no over flow in result

link

answered 08 May '14, 19:28

winux's gravatar image

3★winux
1614
accept rate: 0%

you can get more varied results in modulo operation by taking modulo with large numbers and even more varied if the number is prime. so 10^9 + 7 fits well in this category and this allows tester to be sure to get large range of outputs which is less likely if number is not prime.

link

answered 10 May '14, 02:24

ashwini007k's gravatar image

4★ashwini007k
78791528
accept rate: 6%

can someone give more particular example please ? like for 7500 what should I display?

link

answered 22 Mar '15, 23:45

vishverma94's gravatar image

2★vishverma94
1
accept rate: 0%

As it is the first ten digit prime number and can be suitable to store in 32 bits so it is easy to perform multiplications when the variable is less than 32 bits.

link
This answer is marked "community wiki".

answered 10 Nov, 22:19

nikhil142's gravatar image

2★nikhil142
1
accept rate: 0%

link

answered 14 Nov, 17:32

ricksr's gravatar image

3★ricksr
161
accept rate: 6%

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:

×259

question asked: 08 May '14, 19:15

question was seen: 13,886 times

last updated: 14 Nov, 17:32