以前一直想把伦斯定理好好研究一下，但是一直没有时间，终于得空，现在C实现的代码贴出来，供大家参考一下，其实语言都是次要的，算法的精髓是思想。
求C(n, m) mod 10007[1]
[size=1em]

[size=1em]1 [size=1em]2 [size=1em]3 [size=1em]4 [size=1em]5 [size=1em]6 [size=1em]7 [size=1em]8 [size=1em]9 [size=1em]10 [size=1em]11 [size=1em]12 [size=1em]13 [size=1em]14 [size=1em]15 [size=1em]16 [size=1em]17 [size=1em]18 [size=1em]19 [size=1em]20 [size=1em]21 [size=1em]22 [size=1em]23 [size=1em]24 [size=1em]25 [size=1em]26 [size=1em]27 [size=1em]28 [size=1em]29 [size=1em]30 [size=1em]31 [size=1em]32 [size=1em]33 [size=1em]34 [size=1em]35 [size=1em]36 [size=1em]37 [size=1em]38 [size=1em]39 [size=1em]40 [size=1em]41

[size=1em][size=1em]#include<iostream> [size=1em]#include<cstdio> [size=1em]#include<cstring> [size=1em]#include<cstdlib> [size=1em]#include<set> [size=1em]#include<vector> [size=1em]#include<algorithm> [size=1em]#define ll long long [size=1em]using namespace std; [size=1em]int n,m; [size=1em]const int p=10007; [size=1em]int qpow(int a,int b) [size=1em]{ [size=1em]    int ans; [size=1em]    for(ans=1;b;b>>=1,a=a*a%p) [size=1em]        if(b&1)ans=ans*a%p; [size=1em]    return ans; [size=1em]} [size=1em]int getc(int n,int m) [size=1em]{ [size=1em]    if(n<m)return 0; [size=1em]    if(m>n-m)m=n-m; [size=1em]    ll s1=1,s2=1; [size=1em]    for(int i=0;i<m;i++) [size=1em]    { [size=1em]        s1=s1*(n-i)%p; [size=1em]        s2=s2*(i+1)%p; [size=1em]    } [size=1em]    return s1*qpow(s2,p-2)%p; [size=1em]} [size=1em]int lucas(int n,int m) [size=1em]{ [size=1em]    if(m==0)return 1; [size=1em]    return <a target="_blank" href="/subview/751658/751658.htm">getc</a>(n%p,m%p)*lucas(n/p,m/p)%p; [size=1em]} [size=1em]int main() [size=1em]{ [size=1em]    scanf("%d%d",&n,&m); [size=1em]    printf("%d\n",lucas(n,m)); [size=1em]    return 0; [size=1em]}

以前一直想把伦斯定理好好研究一下，但是一直没有时间，终于得空，现在C实现的代码贴出来，供大家参考一下，其实语言都是次要的，算法的精髓是思想。
求C(n, m) mod 10007[1]
[size=1em]

[size=1em]1 [size=1em]2 [size=1em]3 [size=1em]4 [size=1em]5 [size=1em]6 [size=1em]7 [size=1em]8 [size=1em]9 [size=1em]10 [size=1em]11 [size=1em]12 [size=1em]13 [size=1em]14 [size=1em]15 [size=1em]16 [size=1em]17 [size=1em]18 [size=1em]19 [size=1em]20 [size=1em]21 [size=1em]22 [size=1em]23 [size=1em]24 [size=1em]25 [size=1em]26 [size=1em]27 [size=1em]28 [size=1em]29 [size=1em]30 [size=1em]31 [size=1em]32 [size=1em]33 [size=1em]34 [size=1em]35 [size=1em]36 [size=1em]37 [size=1em]38 [size=1em]39 [size=1em]40 [size=1em]41

[size=1em][size=1em]#include<iostream> [size=1em]#include<cstdio> [size=1em]#include<cstring> [size=1em]#include<cstdlib> [size=1em]#include<set> [size=1em]#include<vector> [size=1em]#include<algorithm> [size=1em]#define ll long long [size=1em]using namespace std; [size=1em]int n,m; [size=1em]const int p=10007; [size=1em]int qpow(int a,int b) [size=1em]{ [size=1em]    int ans; [size=1em]    for(ans=1;b;b>>=1,a=a*a%p) [size=1em]        if(b&1)ans=ans*a%p; [size=1em]    return ans; [size=1em]} [size=1em]int getc(int n,int m) [size=1em]{ [size=1em]    if(n<m)return 0; [size=1em]    if(m>n-m)m=n-m; [size=1em]    ll s1=1,s2=1; [size=1em]    for(int i=0;i<m;i++) [size=1em]    { [size=1em]        s1=s1*(n-i)%p; [size=1em]        s2=s2*(i+1)%p; [size=1em]    } [size=1em]    return s1*qpow(s2,p-2)%p; [size=1em]} [size=1em]int lucas(int n,int m) [size=1em]{ [size=1em]    if(m==0)return 1; [size=1em]    return <a target="_blank" href="/subview/751658/751658.htm">getc</a>(n%p,m%p)*lucas(n/p,m/p)%p; [size=1em]} [size=1em]int main() [size=1em]{ [size=1em]    scanf("%d%d",&n,&m); [size=1em]    printf("%d\n",lucas(n,m)); [size=1em]    return 0; [size=1em]}