Биномиальный коэффициент по модулю 142857

Ответ 1

Алгоритм:

• факторизует базу в основные степени; 142857 = 3 ^ 3 × 11 × 13 × 37
• вычислить результат по модулю каждой простой степени
• объединить результаты, используя теорему китайского останова.

Чтобы вычислить (n above k) mod p^q:

Источник: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf, теорема 1

define (n!)_p как произведение чисел 1..n, которые не делятся на p

определить n_j как n после стирания j наименее значимых цифр в базе p

определить r как n - k

define e_j как число переносов при добавлении k+r, не считая переносов из j младших разрядов, вычисление в базе p

определите s как 1, если p=2 & q>=3 и -1 иначе

затем (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) ), при этом каждый член конкатенации вычисляет одну базовую цифру результата, наименьшее j вычисляет наименее значимые ненулевые цифры.

Ответ 2

Вы можете рассчитать C(n,k) % m в O(n) время для произвольного m.

Трюк состоит в том, чтобы вычислить n!, k! и (n-k)! в качестве векторов первичной мощности, вычесть их позже и перенести остаток по модулю m. Для C(10, 4) мы делаем следующее:

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

Следовательно

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

Мы можем легко вычислить это mod m, так как нет делений. Хитрость заключается в вычислении разложения n! и друзей в линейном времени. Если мы прекомпретируем простые числа до n, мы можем сделать это эффективно следующим образом: Ясно, что для каждого четного числа в произведении 1*2*...*9*10 мы получаем коэффициент 2. Для каждого четвертого числа мы получаем вторую и так далее. Следовательно, число 2 факторов в n! составляет n/2 + n/4 + n/8 + ... (где / - настил). Мы делаем то же самое для остальных простых чисел и потому, что существуют O(n/logn) простые числа меньше n, и мы выполняем O(logn) для каждого, разложение является линейным.

На практике я бы назвал его более неявным следующим образом:

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
}

Это включает в себя сито эратосфенов, поэтому время работы nloglogn, а не n, если простые числа были предварительно рассчитаны или просеяны с более быстрым ситом.

Ответ 3

Что особенно важно в отношении 142857, так это то, что 7 * 142857 = 999999 = 10 ^ 6 - 1. Это фактор, который возникает из маленькой теоремы Ферма с а = 10 и р = 7, что дает модулярную эквивалентность 10 ^ 7 == 10 (mod 7). Это означает, что вы можете работать по модулю 999999 по большей части и сводить к окончательному модулю, делясь на 7 в конце. Преимущество этого заключается в том, что модульное деление очень эффективно в представлениях основания вида 10 ^ k при k = 1,2,3,6. Все, что вы делаете в таких случаях, - это добавить группы цифр; это обобщение изгнание девяток.

Эта оптимизация действительно имеет смысл, если у вас есть умножение на аппаратное обеспечение-10. Который действительно должен сказать, что он работает хорошо, если вы должны сделать это с помощью бумаги и карандаша. Поскольку эта проблема недавно появилась на онлайн-конкурсе, я представляю, что именно происхождение вопроса.