Lucas定理原理、证明及代码模板

落日映苍穹つ 2022-09-09 04:43 162阅读 0赞

### 一、定理 ###

对于素数p，及正整数a、b，当求组合数 C a b C\_a^b Cab对p取余时，如果a和b很大 ( 1 ≤ b ≤ a ≤ 1 0 15 ) (1≤b≤a≤10^\{15\}) (1≤b≤a≤1015)，而p相对较小 ( 1 ≤ p ≤ 1 0 5 ) (1≤p≤10^5) (1≤p≤105)时，我们用Lucas定理来求。

**结论：** C a b ≡ C a p b p ⋅ C a % p b % p C\_\{a\}^\{b\}\\equiv C\_\{\\frac ap\}^\{\\frac bp\}\\cdot C\_\{a\\%p\}^\{b\\%p\} Cab≡Cpapb⋅Ca%pb%p (mod p)

--------------------

### 二、证明 ###

首先将a和b用p进制表示出来  
 a = a 0 p 0 + a 1 p 1 + . . . + a k p k a=a\_0p^0+a\_1p^1+...+a\_kp^k a=a0p0\+a1p1\+...\+akpk b = b 0 p 0 + b 1 p 1 + . . . + b k p k b=b\_0p^0+b\_1p^1+...+b\_kp^k b=b0p0\+b1p1\+...\+bkpk

然后，在证明前，我们要用到**两个引理**。  
（1）p是素数， p ∣ C p k p|C\_p^k p∣Cpk，也就是说p是 C p k C\_p^k Cpk的一个因子。这个很好证明，因为 C p k = p ! k ! ( p − k ) ! C\_p^k=\\frac \{p!\}\{k!(p-k)!\} Cpk=k!(p−k)!p!分子p的阶乘中含有p作为因子，因为p是素数，所以分母中的阶乘都和p互素，那么p就是 C p k C\_p^k Cpk的一个因子了，即p能整除 C p k C\_p^k Cpk。  
（2） ( x + y ) p ≡ x p + y p (x+y)^p\\equiv x^p+y^p (x\+y)p≡xp\+yp (mod p)。这个也很好证明，根据二项式定理将括号拆开可以得 ( x + y ) p = x p + ∑ k = 1 p − 1 C p k x k y p − k + y p (x+y)^p=x^p+\\sum \_\{k=1\}^\{p-1\}C\_p^kx^ky^\{p-k\}+y^p (x\+y)p=xp\+∑k=1p−1Cpkxkyp−k\+yp，而中间项含有 C p k C\_p^k Cpk，是p的整数倍，因此在模p的情况下都可以约掉。就剩下了两边的两项。同理可得： ( x + y ) p k ≡ x p k + y p k (x+y)^\{p^k\}\\equiv x^\{p^k\}+y^\{p^k\} (x\+y)pk≡xpk\+ypk (mod p)

有了这些准备之后，我们再来证明，根据二项式定理将 ( 1 + x ) a (1+x)^a (1\+x)a展开。因为a可以用p进制表示，所以  
 ( 1 + x ) a = ( 1 + x ) a 0 p 0 + a 1 p 1 + . . . + a k p k (1+x)^a = (1+x)^\{a\_0 p^0+a\_1p^1+...+a\_kp^k\} (1\+x)a=(1\+x)a0p0\+a1p1\+...\+akpk ( 1 + x ) a = ( 1 + x ) a 0 × ( 1 + x ) a 1 p × . . . × ( 1 + x ) a k p k (1+x)^a = (1+x)^\{a\_0 \}\\times (1+x)^\{a\_1p\}\\times ...\\times (1+x)^\{a\_kp^k\} (1\+x)a=(1\+x)a0×(1\+x)a1p×...×(1\+x)akpk ( 1 + x ) a ≡ ( 1 + x ) a 0 × ( 1 + x p ) a 1 × . . . × ( 1 + x p k ) a k (1+x)^a \\equiv (1+x)^\{a\_0 \}\\times (1+x^p)^\{a\_1\}\\times ...\\times (1+x^\{p^k\})^\{a\_k\} (1\+x)a≡(1\+x)a0×(1\+xp)a1×...×(1\+xpk)ak  ( 1 + x ) a ≡ ∑ m = 0 a 0 C a 0 m x m × ∑ m = 0 a 1 C a 1 m x p m × . . . × ∑ m = 0 a k C a k m x p k m (1+x)^a \\equiv \\sum \_\{m=0\}^\{a\_0\}C\_\{a\_0\}^mx^m\\times \\sum\_\{m=0\}^\{a\_1\}C\_\{a\_1\}^mx^\{pm\}\\times ...\\times \\sum\_\{m=0\}^\{a\_k\}C\_\{a\_k\}^mx^\{p^km\} (1\+x)a≡m=0∑a0Ca0mxm×m=0∑a1Ca1mxpm×...×m=0∑akCakmxpkm然后我们再看这个同余式**左右两边的 x b x^b xb的系数**。**左边** x b x^b xb的系数是 C a b C\_a^b Cab。再看**右边**，右边所有x的幂都和p进制下的展开是一模一样的，而正好b的p进制是 b = b 0 p 0 + b 1 p 1 + . . . + b k p k b=b\_0p^0+b\_1p^1+...+b\_kp^k b=b0p0\+b1p1\+...\+bkpk，并且右边的每一项都是乘起来的，因此要找 x n x^n xn这一项，当且仅当第一个的i取 b 0 b\_0 b0，第二个i取 b 1 b\_1 b1，…，第k项的i取 b k b\_k bk（他们加起来刚好是b的p进制展开，所以幂次就是b），而他们的每一项的系数就是 C a 0 b 0 C\_\{a\_0\}^\{b\_0\} Ca0b0、 C a 1 b 1 C\_\{a\_1\}^\{b\_1\} Ca1b1、… C a k b k C\_\{a\_k\}^\{b\_k\} Cakbk。因此 x n x^n xn这一项的系数就是将他们乘起来即 C a 0 b 0 × C a 1 b 1 × . . . × C a k b k C\_\{a\_0\}^\{b\_0\}\\times C\_\{a\_1\}^\{b\_1\}\\times ... \\times C\_\{a\_k\}^\{b\_k\} Ca0b0×Ca1b1×...×Cakbk (mod p)。

因此得证，根据左右两边 x n x^n xn的系数相同可得： C a b ≡ C a 0 b 0 × C a 1 b 1 × . . . × C a k b k C\_a^b\\equiv C\_\{a\_0\}^\{b\_0\}\\times C\_\{a\_1\}^\{b\_1\}\\times ... \\times C\_\{a\_k\}^\{b\_k\} Cab≡Ca0b0×Ca1b1×...×Cakbk (mod p)。**时间复杂度**大概是 O ( p log ⁡ N log ⁡ p ) O(p\\log N\\log p) O(plogNlogp)。

--------------------

### 三、代码模板 ###

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    
    int p,n;
    
    int qmi(int a,int b)	//快速幂求逆元
    { 
        LL 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)	//公式求C(a,b)
    { 
        int res = 1;
        for(int i = 1,j = a;i <= b;i++,j--)
        { 
            res = (LL)res * j % p;		//分子从a-b+1乘到a
            res = (LL)res * qmi(i,p-2) % p;	//分母是b的阶乘，转化为乘以阶乘的逆元
        }
        return res;
    }
    
    int lucas(LL a,LL b)	//Lucas定理
    { 
        if(a <p && b < p)	//如果a和b都小于p，可以直接用公式法求c
            return C(a,b);
        return (LL)C(a%p,b%p)*lucas(a/p,b/p) % p;	//否则就用Lucas定理，用Lucas结论来求解
    }
    
    int main()
    { 
        cin >> n;
        while (n -- )
        { 
            LL a,b;
            cin >> a >> b >> p;		//输入a、b和模数p
            cout << lucas(a,b) << endl;
        }
        
        return 0;
    }