lucas

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)

我們求左邊 中的 的係數為：

求右邊公式中的 為：

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

的係數，即

所以

得證。

c++

求C(n, m) mod 10007

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