Lucas[數論定理]:Lucas定理是用來求 c(n,m) mod p -百科知識中文網

定律定義

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

那么：

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

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

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

Lucas定理證明：

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

(1 + x) Ξ(1 + x) Ξ( (1 + x))· (1 + x)Ξ(1 + x) · (1 + x) (mod p)

（modp)

所以得(1 + x)

(mod p)

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

求右邊公式中的為：

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

的係數，即

所以

得證。

c++

求C(n, m) mod 10007

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