Умный алгоритм для нахождения делителей биномиального коэффициента

Question

Мне интересны советы по моему алгоритму, которые я использую, чтобы найти делители очень большого числа, а точнее «n над k» или C (n, k) , Само число может варьироваться очень высоко, поэтому на самом деле нужно учитывать сложность времени в «уравнении», так сказать.

Формула для n над k равна n!/(k! (nk)!), и я понимаю, что я должен попытаться использовать тот факт, что факториалы каким-то образом «рекурсивны», но я все еще не читал слишком много дискретной математики, поэтому проблема заключается в математическом и программировании природа.

Я предполагаю, что я действительно ищу, это лишь некоторые советы, которые направляют меня в правильном направлении - я действительно застрял.

Answer 1

Прежде всего вы можете начать с того, что: C (n, k) = (n/k) C (n-1, k-1).
Вы можете доказать, что C (n, k) делится на n/gcd (n, k).
Если n является простым, то n делит C (n, k).
Проверка теоремы Куммера: если p - простое число, na положительное число и k положительное число с 0 < k < n, то наибольший показатель r, для которого p^r делит C (n, k), - это число необходимых переносов в вычитании nk в базе p.

Предположим, что п> 4:

• если р> п, то р не делит С (п, к), так как в базовом р, п и к только одна цифра широкий → нет переноса в вычитание

• поэтому нам нужно проверить простые делители в [2; n]. Поскольку C (n, k) = C (n, nk), мы можем предположить, что k≤n/2 и n/2≤nk≤n

• для простых делителей в диапазоне] n/2; n] we имеют n/2 < p≤n или эквивалентно p≤n < 2p. Мы имеем p≥2, поэтому p≤n < p², что означает, что n имеет ровно 2 цифры при записи в базе p, а первая цифра должна быть равна 1. Так как k≤n/2 < p, k может быть только одной цифры в ширину. Либо вычитание, как одно переносное, и одно только при n-k < p ⇒ p делит C (n, k); либо вычитание не переносится, а р не делит C (n, k).
  Первый результат:

  каждое простое число] пк; п] является простой делитель С (п, к) с показателем 1.
  не простое число] п/2; пк] не является простой делитель C (n, k).

• in] sqrt (n); n/2] имеем 2p≤n < p², n имеет ровно 2 цифры в ширину в базе p, k < n означает, что k имеет не более 2 цифр. Два случая: только один не переносит вообще. Перенос существует только тогда, когда последняя цифра п больше последняя цифра р IIF п по модулю р < к модулю р Второй результат:

  Для каждого простого числа р в] SQRT (п); п/2] р делит с (п, к) с показателем 1 тогда и только тогда п по модулю р < к модулю р р не делит с (п, к) тогда и только тогда п по модулю р ≥ к модулю р

• в диапазоне [ 2; sqrt (n)], мы должны проверить все простые числа. Это только в этом диапазоне, что простой делитель будет иметь показатель больше 1