lucas定理

高斯-盧卡斯定理，又稱盧卡斯定理，該定理描述了復係數多項式的一個性質：多項式導數的根一定在原多項式的根所構成的凸包內。

這一結論曾在1836被Carl Friedrich Gauss直接使用，1874 得到證明。

Lucas定理是同餘理論中的一個很重要的定理，用於組合數取模。常常使用在問題的結果需要對某個資料取模，n，m很大，達到1e15以上，但是p在1e9以內。一般來說最好的效果實在1e5以內。

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

中文名：盧卡斯定理

外文名：Lucas' Theorem

表示式：C(n，m)%p=C(n/p，m/p)*C(n%p，m%p)%p

提出者：盧卡斯

適用領域：數論（較大的組合數對素數p求模）

應用學科：數學、資訊學

定律定義：

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

那麼：（在程式設計時你只要繼續對 呼叫Lucas定理即可。

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

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