逆元简介

同余符号 ≡
先 bb 一下 ≡，这个符号有三个意思，再这里用到的意思为 “同余符号”。≡ 的介绍
两个整数 a，b，若它们除以整数 m 所得的余数相等，则称 a，b 对于模 m 同余
记作 a≡b(mod m)
读作 a 同余于 b 模 m，或读作 a 与 b 关于模 m 同余。
比如 26≡14(mod 12)。
什么是逆元
如果一个线性同余方程 ax ≡ 1(mod b) ，则 x 称为 a mod b 的逆元.
逆元的含义
模 b 意义下，1 个数 a 如果有逆元 x，那么除以 a 相当于乘以 x。
也就是 (a/b)%p=(ax)%p=(a%p)(b%p)%p

~ 那么问题来了，这逆元有啥用吗，这个问题问的好啊~
如果我们要求一个组合数 C(n,m)%p=(n!/(n-m)!*m!)%p, 但是取模的性质对于除法不适用啊。
【逆元求组合数】 - 图1

但当这个 n 和 m 很大时又不得不取模，不取模就会溢出。所以就可以用逆元来把乘法代替除法。

怎么求逆元

暴力 O(P) 求逆元
先举这个最简单最暴力的方法，这样便于理解逆元。具体思路就是枚举 1~p-1，检查是否有符合条件的 a*x=1(mod p)。时间复杂度为 O（P）。

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int main()
  5. {
  6.     int a,p;
  7.     cin>>a>>p;
  8.     for(int x=1;x<p;x++){
  9.         if(x*a%p==1) {
  10.             printf("%d\n",x);
  11.             break;
  12.         }
  13.     }
  14.     return 0;
  15. }

扩展欧几里得法
给定模数 p，求 a 的逆元相当于求解 ax=1(mod p)
这个方程可以转化为 ax-py=1
然后套用求二元一次方程的方法，用扩展欧几里得算法求得一组 x0,y0 和 gcd (最大公约)
检查 gcd 是否为 1
gcd 不为 1 则说明逆元不存在 ，若为 1，则把 x0 调整到 0~m-1 的范围中即可
（ ①：extgcd 目的 求 x ,y ； ②：逆元 目的 求 x ）
一个数有逆元的充分必要条件是 gcd(a,n)=1，如果 gcd(a,n)>1, 则不存在逆元

  1. int exgcd(int a,int b,int &x,int &y)
  2. {
  3.     if(b==0) {
  4.         x=1,y=0;
  5.         return a;
  6.     }
  7.     int r = exgcd(b,a%b,x,y);
  8.     int t = x;
  9.         x = y;
  10.         y = t - a/b*y;
  11.     return r;
  12. }

快速幂法

这个要运用 费马小定理 ：
【逆元求组合数】 - 图2

再看看推导过程：
【逆元求组合数】 - 图3

由以上推导就可以通过求一个幂运算很简单的求出逆元辽。

上一个代码，具体功能就是求 n 和 m 的组合数 mod1e9+7

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. typedef long long ll;
  5. const ll Mod=1e9 + 7;
  6. ll fac[100010];
  7. ll inv[100010];
  9. ll quick(ll a,int b)
  10. {
  11.     ll ans=1;
  12.     while(b)
  13.     {
  14.         if(b&1)ans=(ans*a)%Mod;
  15.         a=a*a%Mod;
  16.         b>>=1;
  17.     }
  18.     return ans;
  19. }
  21. void getfac()
  22. {
  23.     fac[0]=inv[0]=1;
  24.     for(int i=1;i<=100000;i++)
  25.     {
  26.         fac[i]=fac[i-1]*i%Mod;
  27.         inv[i]=quick(fac[i],Mod-2); 
  28.     }
  29. }
  31. ll getans(ll n,ll m)
  32. {
  33.     return fac[n]*inv[n-m]%Mod*inv[m]%Mod;
  34. }
  36. int main()
  37. {
  38.     getfac();
  40.     ll n,m;
  41.     while(cin>>n>>m)
  42.     {
  43.         ll ans=getans(n,m);
  44.         cout<<ans<<endl;
  45.     } 
  46. }

Lucas 定理

对于大组合数取模，n,m 不大于 10 ^ 5 的话，用逆元的方法，可以解决。对于 n,m 大于 10 ^ 5 的话，那么要求 p<10 ^ 5，这样就是 Lucas 定理了，将 n,m 转化到 10^5 以内解。
Lucas 定理是用来求 c(n,m) mod p，p 为素数的值。
C(n,m)%p=C(n/p,m/p)C(n%p,m%p)%p
也就是 Lucas(n,m)%p=Lucas(n/p,m/p)C(n%p,m%p)%p
求上式的时候，Lucas 递归出口为 m=0 时返回 1，原因是因为Lucas(a,0,q)=1;
模板：

  1. #include <cstdio>  
  2. #include <iostream>  
  3. #include <cmath>  
  4. #include <cstring>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. #define maxn 100010  
  8. typedef long long LL;  
  9. LL m,n,p;  
  10. LL Pow(LL a,LL b,LL mod)  
  11. {  
  12.     LL ans=1;  
  13.     while(b)  
  14.     {  
  15.         if(b&1)ans=(ans*a)%mod;
  16.         a=a*a%mod;
  17.         b>>=1;
  18.     }  
  19.     return ans;  
  20. }  
  21. LL C(LL n,LL m)  
  22. {  
  23.     if(n<m)  
  24.         return 0;  
  25.     LL ans=1;  
  26.     for(int i=1;i<=m;i++)  
  27.     {  
  28.         ans=ans*(((n-m+i)%p)*Pow(i,p-2,p)%p)%p;  
  29.     }  
  30.     return ans;  
  31. }  
  32. LL Lucas(LL n,LL m)  
  33. {  
  34.     if(m==0)  
  35.         return 1;  
  36.     return (Lucas(n/p,m/p)*C(n%p,m%p))%p;  
  37. }  
  38. int main()  
  39. {  
  40.     int t;  
  41.     scanf("%d",&t);  
  42.     while(t--)  
  43.     {  
  44.         scanf("%lld%lld%lld",&n,&m,&p);  
  45.         printf("%lld\n",Lucas(n,m));  
  46.     }  
  47.     return 0;  
  48. }

https://blog.csdn.net/m0_46193982/article/details/105008799

https://blog.csdn.net/m0_46193982/article/details/105008799