卢卡斯定理（Lucas定理）的绝妙证明

· · 题解

网上对 Lucas 定理的证明基本上都是用二项式定理推式子，也有人用母函数证明，不过本蒟蒻感觉我这个证明太妙了，比那些证明都直观、好懂。（可惜地方太小了写不下）所以说即使这道题已经关闭题解提交了，我还是想联系管理员发题解。

Lucas定理：

C_{n}^{m}\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\cdot C_{n (mod\,p)}^{m(mod\,p) } (mod\,p)

其中\lfloor~\rfloor表示向下取整

前置知识：扩展欧几里得定理、逆元，当 a 和 p 互质时 a 在 mod~p 意义下的逆元唯一。

证 Lucas 定理之前首先说一下不用 Lucas 定理的做法，就是把 C_n^m 写成

C_n^m=\frac{(n-m+1)(n-m+2) \cdots n}{1\times2 \cdots m}

然后分开考虑 p 的倍数部分和不是 p 的倍数的部分，统计分子分母的质因数 p 的幂次，看看C_n^m 是不是 p 的倍数，然后不是 p 的倍数的部分就乘起来，分母的逆元乘上分子就行了。

引理：C_n^m 是整数

这部分的证明跟证明 C_n^m 是整数的方法挺像的，如果会了的话可以跳到下面的证明核心部分。

看这部分之前可以先看看如何用数论方法证明 C_n^m 是整数，方法也是对于每个质数 p，统计分子和分母 p 的幂次，然后证明分子的幂次一定大于等于分母的幂次。

那么怎么统计质数 p 的幂次呢？根据 莫比乌斯反演 容斥原理，要求一些数的乘积中质数 p 的幂次，就是把 p 的倍数找出来除以 p ，除完之后再把 p 的倍数找出来除以 p ，循环直到所有数都不是 p 的倍数，所以 p 的幂次就等于

p的倍数数量+p^2的倍数数量+p^3的倍数数量+\cdots

接下来的问题就是对于任何一个数 k，要统计 1 到 m 和 n-m+1 到 n 中 k 的倍数有多少个， 1 到 m 就有 \lfloor \frac m k \rfloor 个数是 k 的倍数， n-m+1 到 n 中有 (\lfloor \frac n k \rfloor-\lfloor \frac {n-m} k \rfloor) 个

这里我设 k=5，要统计 5 的倍数，我画了个图，看看 1 到 m 和 n-m+1 到 n 这两个区间各覆盖了多少个 k 的倍数。可以发现 n-m+1 到 n （分子）中 k 的倍数数量一定大于等于 1 到 m （分母）中 k 的倍数数量，二者可能相等也可能相差 1 ，所以说分子中 p 总幂次 =p的倍数数量+p^2的倍数数量+p^3的倍数数量+\cdots 一定 \geq 分母中的，这就证明了组合数 C_n^m 一定为整数。然后 p 的倍数数量、p^2 的倍数数量、p^3 的倍数数量 \cdots 里只要有任何一个是分子大于分母的，分子的 p 总幂次就会大于分母的 p 总幂次。

再看这个图，当 n=18 或者 n=19 的时候分子中只有 15 是 5 的倍数，可以证明当且仅当 n\%p<m\%p 时，分子中 p 的倍数数量 \geq 分母中 p 的倍数数量，那么再看Lucas定理右式，这个时候 C_{n\%p}^{m\%p} 上面大于下面，这个组合数就得 0 了，Lucas定理的左边和右边就都是 0 。

证明核心部分

接下来考虑 n\%p \geq m\%p 的情况，上面本蒟蒻借鉴了证明 C_n^m 的方法，但是下面的方法就是我原创的了。（但是查了Google发现我不是最早研究出来这个新证明方法的，好难受）

数论里跟取模有关的事情经常会出现循环，那么组合数取模写出来之后也能发现循环，这里我举了 p=3,n=17,m=7 的例子画图，把 C_n^m=\frac{(n-m+1)(n-m+2) \cdots n}{1\times2 \cdots m} 里面的数列了出来，之后，然后把p的倍数圈起来，想分成 p 的倍数和不是 p 的倍数两部分考虑。

圈起来的 p 的倍数部分每个数除以 p 之后就变成连续的一段了，分子就是从 1 乘到 \lfloor \frac m p \rfloor ，而分母是从 \lfloor \frac n p \rfloor 开始往下数，一共 \lfloor \frac m p \rfloor 个数乘起来，所以说这部分就等于C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}

然后考虑剩下的不是 p 的倍数的部分，根据逆元唯一性，中间除以 p 的余数相同的部分全都可以直接划掉，就剩下两边，不难证明，两边的部分就同余于 C_{n\%p}^{m\%p}

那么分类讨论的两种情况都有 C_{n}^{m}\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\cdot C_{n (mod\,p)}^{m(mod\,p) } (mod\,p) ，直接就证完了。

直接上代码，代码还是挺简单的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mn=1e5;

ll 幂(ll a,ll b,ll p) {
    a%=p;
    ll ans=1%p;
    while(b>0) {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll 逆元(ll a,ll p) {
    return 幂(a,p-2,p);
}

int n,m,p,T;
ll 阶乘[mn+3],阶乘逆[mn+3];
ll C(int n,int m,int p) {
    if(n<m) return 0;
    if(n<p&&m<p) 
        return 阶乘[n]*阶乘逆[m]%p*阶乘逆[n-m]%p;
    return C(n/p,m/p,p)*C(n%p,m%p,p)%p;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("Lucas.in","r",stdin);
    #endif
    cin>>T;
    while(T--) {
        cin>>m>>n>>p;
        n+=m;
        阶乘[0]=1%p;
        for(int i=1;i<=p-1;i++) 阶乘[i]=阶乘[i-1]*i%p;
        阶乘逆[p-1]=逆元(阶乘[p-1],p);
        for(int i=p-1;i>=1;i--) 阶乘逆[i-1]=阶乘逆[i]*i%p;
        cout<<C(n,m,p)<<endl;
    }
    return 0;
}

注：实际我的思考过程和证明的呈现顺序不一样，很多数学教材也是这样，这样会感觉思维比较跳跃，其实可以把引理放到后面。