Binomial coefficient modulo 142857

问题:

How to calculate binomial coefficient modulo 142857 for large n and r. Is there anything special about the 142857? If the question is modulo p where p is prime then we can use Lucas theorem but what should be done for 142857.

回答1:

The algorithm is:

• factorise the base into prime powers; 142857 = 3^3×11×13×37
• compute the result modulo each prime power
• combine the results using the Chinese Remainder Theorem.

---

To compute (n above k) mod p^q:

Source: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf, theorem 1

define (n!)_p as the product of numbers 1..n that are not divible by p

define n_j as n after erasing j least significant digits in base p

define r as n-k

define e_j as the number of carries when adding k+r, not counting the carries from j lowest digits, computing in base p

define s as 1 if p=2 & q>=3 and -1 otherwise

then (n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)( (n_j!)_p / ((k_j!)_p*(r_j!)_p) ) with each term of the concatenation computing one base-p digit of the result, lowest j computing the least significant non-zero digits.

回答2:

You can actually calculate C(n,k) % m in O(n) time for arbitrary m.

The trick is to calculate n!, k! and (n-k)! as prime-power-vectors, subtract the two later from the first, and multiply the remainder modulo m. For C(10, 4) we do this:

10! = 2^8 * 3^4 * 5^2 * 7^1
 4! = 2^3 * 3^1
 6! = 2^4 * 3^2 * 5^1

Hence

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1

We can calculate this easily mod m as there are no divisions. The trick is to calculate the decomposition of n! and friends in linear time. If we precompute the primes up to n, we can do this efficiently as follows: Clearly for each even number in the product 1*2*...*9*10 we get a factor of 2. For each fourth number we get a second on and so forth. Hence the number of 2 factors in n! is n/2 + n/4 + n/8 + ... (where / is flooring). We do the same for the remaining primes, and because there are O(n/logn) primes less than n, and we do O(logn) work for each, the decomposition is linear.

In practice I would code it more implicit as follows:

func Binom(n, k, mod int) int {
    coef := 1
    sieve := make([]bool, n+1)
    for p := 2; p <= n; p++ {
        if !sieve[p] {
            // Sieve of Eratosthenes
            for i := p*p; i <= n; i += p {
                sieve[i] = true
            }
            // Calculate influence of p on coef
            for pow := p; pow <= n; pow *= p {
                cnt := n/pow - k/pow - (n-k)/pow
                for j := 0; j < cnt; j++ {
                    coef *= p
                    coef %= mod
                }
            }
        }
    }
    return coef
}

This includes a Sieve of Eratosthenes, so the running time is nloglogn rather than n if the primes had been precalculated or sieved with a faster sieve.

回答3:

What's special about 142857 is that 7 * 142857 = 999999 = 10^6 - 1. This is a factor that arises from Fermat's Little Theorem with a=10 and p=7, yielding the modular equivalence 10^7 == 10 (mod 7). That means you can work modulo 999999 for the most part and reduce to the final modulus by dividing by 7 at the end. The advantage of this is that modular division is very efficient in representation bases of the form 10^k for k=1,2,3,6. All you do in such cases is add together digit groups; this is a generalization of casting out nines.

This optimization only really makes sense if you have hardware base-10 multiplication. Which is really to say that it works well if you have to do this with paper and pencil. Since this problem recently appeared on an online contest, I imagine that's exactly the origin of the question.