-2

I'm stuck in a problem in which I need to calculate something like:

((500!)/(20!x20!x20!x20!...)) mod 1000000007

I understand how to calculate 500!%1000000007 but I am not sure on how to distribute that operator in division.

I am currently trying to write a code which cancels the denominators by its numerator by its factors. But I am not sure if it is a good approach to this.

I just need a mathematical way of solving these kind of problems(mod1000000007) as they are regularly encountered in programming competitions and would help me to prepare for Google Code Jam.

daerty0153
  • 524
  • 1
  • 6
  • 11
  • 1
    What does `(x/y) mod z` even mean? Is it: "find a number, which if multiplied by `y`, will be equal (mod `z`) to `x`?" – Aaron McDaid Feb 09 '12 at 23:21
  • Exact duplicate of http://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions – nikhil Jul 02 '12 at 14:36

1 Answers1

4

Method 1:

Think of how you would compute 500! / (20! * 20! * 20! * ...) normally.

Don't multiply everything out and divide at the end. Do your divisions in the middle. Then combine this with the modulus reductions from your previous question.

Method 2:

Prime factorize 500! and 20!. Then subtract out the prime factors of 20! * 20! * 20! (or how ever many of them you have) from the prime factors of 500!.

Then rebuild the number by multiplying back the remaining factors together. (while taking modulus along the way to keep the number from getting large)

Method 3:

If 1000000007 (or whatever modulus) is prime, you can do divisions using the modular inverse.

Compute 20! mod 1000000007. Then compute it's modular inverse and multiply it into 500! mod 1000000007.

Mysticial
  • 464,885
  • 45
  • 335
  • 332
  • thanks a lot. Method3 helps a lot. Could you also suggest me a good book to improve my math skills, which are essential to programming i.e. difficult to solve otherwise. – daerty0153 Feb 09 '12 at 23:30
  • 1
    I don't read books. I use Google and Wikipedia. This math topic that you've stumbled upon is called "Number Theory". But that's a very large topic that no single book can cover. You can also try searching for "Modular Arithmetic". – Mysticial Feb 09 '12 at 23:33