Lacus定理—-求较大组合数
之前介绍的费马小定理,用来处理$C(n,m)$组合数取模$p$,要求$p$为质数,$n,m$小于$1e5$(应该是受阶乘数组限制,$1e6$差不多也行)
当$n、m$达到1e8、1e10甚至更大的时候怎么办呢?这时候就需要Lacus定理。
Lacus定理
重点:可以解决$n、m$比较大,$p$为质数且较小的组合数问题
(我看这个博客讲的比较简单,一眼就能懂)
性质:
A、B是非负整数,p是质数。AB写成p进制:A=a[n]a[n-1]…a[0],B=b[n]b[n-1]…b[0]。
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…*C(a[0],b[0]) modp同余
即:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) (递归基础)
非常简单,上代码:
1 | /* |