Я пытаюсь вычислить nCr по модулю p, где p - простое число.Вычисление nCr по модулю p, простое
Один из подходов, который я пробовал, - это вычислить n!/(r! * (n-r)!) по модулю p с использованием мультипликативных обратных, но это не удается, если либо r, либо n - r больше или равно p, так как тогда факториалы равны нулю по модулю p, а обратные не существуют.
Какой метод работает во всех случаях, а не только при наличии мультипликативных инверсий?
Я бы использовать Lucas's theorem
C(14,1), p=13
N = 14 = 1 * 13 + 1
K = 1 = 0 * 13 + 1
C(N,K) mod p = (C(1,0) mod 13) * (C(1,1) mod 13) = 1
Это то, что мне нужно .... .thanks много @MBo – Ashwini
Вычисление Ncr по модулю р, р простое число
Другой метод: Вы также можете использовать паскаль метод для расчета Ncr
Как для любого Ncr, вы можете использовать
row[0]=1;
for(i=1;i<n/2;i++)
{
row[i]=row[i-1]*(n-i+1)/i
}
for(i=n/2;i<=n;i++)
{
row[i]=row[n-i]
}
В этом вы должны принять modulo_inverse из (I) с использованием любого из выше способом (Fermat's little theorem или Extended Euclidean algorithm)
порядковый номер: Best known algos for calculating nCr % M
«Этот алгоритм даст nCr = 0 для каждого n, большего чем p, так как mod factorial станет равным нулю. Но это неправильный расчет. Ex. 14C1 mod 13 = 1, а не 0. «Как вы получаете 0 с помощью вашего алгоритма? – IVlad
' f [n] * ((InverseEuler (f [r], p) * InverseEuler (f [nr], p))% p))% p', где 'f [n] (n!% p)' и InverseEuler (a, b) есть '((a^(p-2))% p)'. Это была бы дискретная формула для nCr, используя теорему Эйлера для модулярного мультипликативного обратного. f [n] при n> = p будет равна нулю, и, следовательно, значение nCr станет равным нулю. Исправьте меня, если я ошибаюсь. @IVlad – Ashwini
Эта формула работает только для 'f [x], p' coprime. Умножения 'p' не являются взаимно простыми с' p'. – IVlad