定义

若 \(p\) 为质数，且\(a\ge b\ge1\)，则有：

\[C_{a}^{b}\equiv C_{a/p}^{b/p}\cdot C_{a (mod\,p)}^{b(mod\,p)} \]

拆分a与b

按照 \(p\) 进制拆分 \(a\) 与 \(b\) ,设 \(a\) 与 \(b\) 是 \(k\) 位，不足用 \(0\) 补足。

\[\left\{\begin{aligned} a&=a_0p^{0}+a_1p^{1}+\cdots+a_{k-1}p^{k-1}+a_kp^{k}\\ b&=b_0p^{0}+b_1p^{1}+\cdots+b_{k-1}p^{k-1}+b_kp^{k} \end{aligned}\tag{1} \right. \]

证明\((1+x)^{p}\equiv1+x^p\,mod\,p\)

根据二项式定理有：

\[\begin{aligned} (1+x)^p&=C_p^0x^0+C_p^1x^1+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+C_p^px^p\\ &=1+C_p^1x+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+x^p\\ \end{aligned} \]

\(\because p为质数\therefore1\sim p-1均与p互质\\\therefore C_p^2,C_p^3,\cdots,C_p^{p-1}均能整除p,即C_p^2,C_p^3,\cdots,C_p^{p-1}\,mod\,p=0\)

\[(1+x)^p\equiv(1+x^p)\,mod\,p\tag{2} \]

即 \((1+x)^p\) 在模 \(p\) 的意义下与 \((1+x^p)\) 同余。

根据 \((1+x)^a\) 求解 \(C_b^a\)

设 \(a=\lfloor \frac{a}{p}\rfloor p+a\%p\)，\(a'=\lfloor \frac{a}{p}\rfloor\) 有：

\[\begin{aligned} (1+x)^a&=(1+x)^{\lfloor \frac{a}{p}\rfloor p+a\%p}\\ &=(1+x)^{a'p+a\%p}\\ &=(1+x)^{a'p}(1+x)^{a\%p}\\ \because a\%p=a_0 \therefore &=(1+x)^{a'p}(1+x)^{a_0}\\ &=\underline{((1+x)^p)^{a'}}(1+x)^{a_0}\\ \because公式(2) \therefore &=\underline{(1+x^p)^{a'}(1+x)^{a_0}} \end{aligned}\tag{3} \]

再设 \(a'=\lfloor \frac{a'}{p}\rfloor p+a'\%p\)，\(a''=\lfloor \frac{a'}{p}\rfloor\) 有：

\[\begin{aligned} ((1+x)^p)^{a'}&=(1+x^p)^{\lfloor \frac{a'}{p}\rfloor p+a'\%p}\\ &=(1+x^p)^{a''p+a'\%p}\\ &=(1+x^p)^{a''p}((1+x)^p)^{a'\%p}\\ \because a'\%p=a_1 \therefore &=(1+x^p)^{a''p}((1+x)^p)^{a_1}\\ &=\underline{(1+x^p)^p)^{a''}((1+x)^p)^{a_1}}\\ \because公式(2) \therefore &=\underline{(1+x^{p^2})^{a''}(1+x^p)^{a_1}} \end{aligned}\tag{4} \]

同理，可得到

\[(1+x^{p^2})^{a''}=(1+x^{p^3})^{a'''}\underline{(1+x^{p^2})^{a_2}} \]

这样经过不断的迭代，最终得到:

\[(1+x)^a=(1+x^{p^k})^{a_k}*(1+x^{p^{k-1}})^{a_{k-1}} *\cdots*(1+x^p)^{a_1}*(1+x)^{a_0}\tag{5} \]

等式两边运用二项式分别求 \(C_a^bx^b\) ,右边可以看作 \(b\) 个球分到了 \(k\)个 盒子里，每个盒子里面得数量就是 \(b_i(1\le i\le k)\) 得

\[\begin{aligned} C_a^bx^b&=C_{a_k}^{b_k}x^{p^kb_k}C_{a_{k-1}}^{b_{k-1}}x^{p^{k-1}b_{k-1}}\cdots C_{a_1}^{b_1}x^{pb_1}C_{a_0}^{b_0}x^{b_0}\\ &=(\prod_{i=0}^k{C_{a_i}^{b_i}})(x^{\sum_{i=0}^{k}{p^ib_i}})\\ \because 公式(1)中b的展开式 \therefore &=(\prod_{i=0}^k{C_{a_i}^{b_i}})x^b\\ \end{aligned} \]

等式两边同时消去 \(x^b\) ，得：

\[C_a^b\,mod\,p\equiv \prod_{i=0}^{k}{C_{a_i}^{b_i}}\tag{6} \]

根据递归的过程，也可写成：

\[C_a^b\,mod\,p=C_{a/p}^{b/p}C_{a\%p}^{b\%p}\tag{7} \]

例题：

下面以AcWing 887. 求组合数 III为例：传送门

• 使用 \(Lucas\) 定理主要使用公式\(7\)的递推式
• 函数int C(int a, int b)实现\(C_a^b\)的求解，使用\(C_a^b=\frac{a*(a-1)*\cdots*(a-b+1)}{b*(b-1)*\cdots*1}\),分子用逆元即可
• 参考y总：传送门

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int p;
int qmi(int a, int b) {
    int res=1;
    while(b) {
        if(b&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}
int C(int a, int b) {
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j) {
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2)%p;
    }
    return res;
}
int lucas(ll a, ll b) {
    if(a<p&&b<p) return C(a,b);
    return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main() {
    #ifdef ONLINE_JUDGE
    #else
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // ONLINE_JUDGE
    scanf("%d",&n);
    while(n--) {
        ll a,b;
        scanf("%lld%lld%lld",&a,&b,&p);
        printf("%d\n",lucas(a,b));
    }
    return 0;
}