Fast algorithm to calculate n! / (q!)^r

Since you have a low upper bound on n, it’s possible to start off by factoring all of the numbers in the range [1, 3 × 106]. There are many ways to do this reasonably efficiently. One way to do this is to use the Sieve of Eratosthenes or a related sieve to find all the prime numbers less than 3 × 106, then use a DP algorithm: mark 1 has having just itself as a prime factorization, and then for each number 2, 3, 4, 5, 6, …, 3 × 106, try dividing those numbers by the primes, in sequence, until you find one that divides cleanly, leaving a remainder of r. The prime factorization of that number will then be the prime factorization of r, times the prime number you divided out.

Once you have the prime factorization of all of these numbers, you can efficiently compute the prime factorization of n! using the prime factorization of the numbers 1, 2, 3, …, n. To do this, you can just add up all of the exponents of the corresponding primes in the factorization of the numbers 1, 2, 3, …, n. You can similarly compute a prime factorization for q!, and then get a prime factorization for (q!)r by multiplying all the exponents in the prime factorization of q! by r.

Once you have these prime factorizations, you can then compute n! / (q!)r by simply doing a pairwise subtraction of all of the exponents in the prime factorization of n! by the corresponding exponents in the prime factorization of (q!)r. You can then recover the value of n! / (q!)r by multiplying all of these numbers together.

If you need an exact value, then you will probably spend more work multiplying all of the factors together than actually finding those factors. If you only need the value modulo some large prime, then this method will be very efficient and will give you an exact answer, as long as you mod by that large prime as you multiply all the factors together.

Hope this helps!

Browse More Popular Posts

Leave a Comment