数论：Lucas（卢卡斯）定理

女爷i 2023-01-13 10:54 265阅读 0赞

## Lucas（卢卡斯）定理 ##

**Lucas定理**：用来求 c(n,m) mod p，p是素数的值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70 2][]

### **代码实现：求C(n, m) mod 10007** ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    const long long p=10007;
    
    long long n,m;
    
    long long mod_pow(long long x,long long y)
    
    {
    
    long long a=1;
    
    while (y)
    
    {
    
    if (y&1) a=a*x%p;
    
    x=x*x%p;
    
    y>>=1;
    
    }
    
    return a;
    
    }//运用费马小定理结合快速幂求x mod y时的逆元 
    
    long long C(long long n,long long m)
    
    {
    
    if (m>n) return 0;
    
    long long C1=1,C2=1;//组合数公式中的分子分母
    
    for (int i=n-m+1;i<=n;++i) C1=C1*i%p;
    
    for (int i=1;i<=m;++i) C2=C2*i%p;
    
    return C1*mod_pow(C2,p-2)%p; 
    
    }//求C(n,m)的值 
    
    long long Lucas(long long n,long long m)
    
    {
    
    if (!m) return 1;
    
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
    
    }
    
    int main()
    
    {
    
    scanf("%lld %lld",&n,&m);//求解C(n,m) mod 10007
    
    printf("%lld\n",Lucas(n,m)); 
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/81e7d8202dfc4c2e952ada2870826dba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/e557bc3062454761a16173589a92f13c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/db2ea92555824611819d30ecf3ba0d95.png