Ash*_*ini 4 algorithm math combinations
我正在尝试计算nCr模p,其中p是素数.
我尝试过的一种方法是计算n!/(r!*(nr)!)模p使用乘法反转,但当r或n -r大于或等于p时,这会失败,因为因子则是零模p并且反转不存在.
什么方法适用于所有情况,而不仅仅是在存在乘法反转的情况下？
我会用卢卡斯定理
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
| 归档时间： |
|
| 查看次数： |
847 次 |
| 最近记录： |