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)：）