lucas(數論定理)

Lucas定理是用來求 c(n,m) mod p，p為素數的值。

基本介紹

• 中文名：盧卡斯定理
• 外文名：Lucas' Theorem
• 表達式：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
• 提出者：盧卡斯
• 套用學科：數學，信息學
• 適用領域範圍：大組合數求模
• 適用領域範圍：數論

定律定義

Lucas定理：我們令n=sp+q , m=tp+r .（q ，r ≤p）

那么：

（在編程時你只要繼續對 調用Lucas定理即可。

代碼可以遞歸的去完成這個過程，其中遞歸終點為t = 0 ；

時間O（log_p(n)*p)：）

推導過程

Lucas定理證明：

首先你需要這個算式: ,其中f > 0&& f < p，然後

(1 + x) ⁿΞ(1 + x) ^sp+q Ξ( (1 + x)^p)^s· (1 + x) ^q Ξ(1 + x^p) ^s· (1 + x) ^q(mod p)
　　

（modp)

所以得(1 + x) ^sp+q (mod p)
　　

我們求左邊(1 + x)^sp+q 中的 的係數為：

求右邊公式中的 為：

通過觀察你會發現若且唯若i = t , j = r ,能夠得到 的係數，即
　　

　

所以

得證。

代碼實現

c++

求C(n, m) mod 10007

int Lucas (ll n , ll m , int p) {  return m == 0 ? 1 : 1ll*comb (n%p , m%p , p) * Lucas (n/p,m/p,p)%p ;}//comb()函式中，因為q ， r < p , 所以這部分暴力完成即可。//C++求C(n, m) mod 10007    版本二 要求p z在100000左右ll f[N];void init(int p) {       //f[n] = n!    f[0] = 1;    for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;} ll pow_mod(ll a, ll x, int p){    ll ret = 1;    while (x)        {        if (x & 1)  ret = ret * a % p;        a = a * a % p;        x >>= 1;    }    return ret;} ll Lucas(ll n, ll k, int p)        //C (n, k) % p{     ll ret = 1;     while (n && k)         {        ll nn = n % p, kk = k % p;        if (nn < kk) return 0;  //inv (f[kk]) = f[kk] ^ (p - 2) % p        ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;        n /= p, k /= p;     }     return ret;}int main(void){    init (p);    printf ("%I64d\n", Lucas (n, m, p));    return 0;}

見右圖，參考馮志剛《初等數論》第37頁。