数论之Lucas定理求大组合数取模的应用常见题型汇总
Lucas定理是用来求 c(n,m) mod p,p为素数的值。 对于C(n, m) mod p。这里的n,m,p(p为素数)都很大的情况。就不能再用C(n, m) = C(n - 1,m) + C(n - 1, m - 1)的公式递推了。 应用:大组合数求模 表达式C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p 因为p为素数,所以这类题都可以用费马小定理计算逆元。当然...