9

I was working on a problem which requires output as "For each line output the answer modulo 10^9+7". Why is modulo 10^9+7 included in the problem? What is its significance?

I'm not looking for a solution to the problem; only the significance of that particular constant.

Toby Speight
  • 27,591
  • 48
  • 66
  • 103
Shubham Marathia
  • 176
  • 1
  • 2
  • 11
  • Are you asking what the value of the number is (1000000007), or how modular arithmetic works? – Mike Seymour Sep 05 '14 at 15:25
  • I am asking what it means in the problem's context.See this http://www.codechef.com/SEPT14/problems/CHEFLR . I am not asking for a solution to that problem but just this modulo 10^9+7. @MikeSeymour – Shubham Marathia Sep 05 '14 at 15:26
  • If you're asking whether 10^9+7 is some special number that's relevant to the problem--I don't think so. I think the problem setter just sort of came up with it at random. – ajb Sep 05 '14 at 15:31
  • OK, after seeing @tmyklebu's answer, I can see that it's not quite random. – ajb Sep 05 '14 at 15:38
  • Possible duplicate of [What's the idea of doing x mod 1000000007?](http://stackoverflow.com/questions/12578376/whats-the-idea-of-doing-x-mod-1000000007) – phuclv May 17 '17 at 15:26

3 Answers3

22

Problems ask for results modulo primes because the alternatives, namely asking for a floating-point result giving the "high-order bits" and asking for the whole result, aren't always what the problem setter is looking for.

  • These problems are often "find and implement a recurrence" problems. The low-order bits will often tell you whether the recurrence you found is right.
  • There may be a special trick for the "high-order bits" problem, perhaps based on a clever analytic approximation.
  • The reason people don't often ask for the whole result is that this requires the contestant to implement big-number arithmetic.
  • Problem setters usually don't want unexpected tricks to crack their problems for "the wrong reasons."

10^9+7 winds up being a pretty good choice of prime. It is a "safe prime." What that means:

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.

More than that, 10^9+6, which is 10^9+7-1, is twice a prime. So the multiplicative group modulo 10^9+7 doesn't decompose into small things and hence no Chinese-remainder-like trick applies there.

Toby Speight
  • 27,591
  • 48
  • 66
  • 103
tmyklebu
  • 13,915
  • 3
  • 28
  • 57
  • 1
    Side note: I'd love it if people asked for the high-order bits instead of the low-order bits in enumeration problems. There's something of an art to finding good analytic approximations to these sorts of problems and I think it's underappreciated in programming contests. – tmyklebu Sep 05 '14 at 15:43
2

In some problems the answers are very big numbers, but forcing you to implement long arighmetics is not the purpose of the problem authors. Therefore they ask you to calculate answer modulo some number, like 1000000007, so you don't have to implement long arithmetics, but the answer is still verifiable.

Anton Savin
  • 40,838
  • 8
  • 54
  • 90
0

If it was asked to give answer as modulo 10^9 you could mask the bits easily but to make problems more tough a number such as 10^9+7 is choosen

Abhishek Ranjan
  • 238
  • 2
  • 14