首页 > 代码库 > 逆元基本知识

逆元基本知识

2024-09-12 23:34:33   216人阅读

逆元的用处，ans = (a/b) % mod;

但是ans != (a%mod) / (b %mod)

因此我们 可以把ans 转化为 ans = a * inv（b，mod） % mod

inv(b,mod) 的含义为  b 对于 mod 的逆元 令 inv(b,mod) = x;

转化为同余方程就是 bx ≡ 1（% mod）

当 b 与 mod 互质的时候有两种方法求 inv（b,mod）

单个元素逆元

①扩展欧几里得

　　解不定方程 bx + mody = 1 其中 x的值即为 inv（b,mod）

　　学习一个 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

技术分享 
 1 int exgcd(int a,int b,int &x,int &y)
 2 {
 3     if(b==0)
 4     {
 5         x=1;
 6         y=0;
 7         return a;
 8     }
 9     int r=exgcd(b,a%b,x,y);
10     int t=x;
11     x=y;
12     y=t-a/b*y;
13     return r;
14 }
扩展欧几里得代码

②费马小定理 百度百科 费马小定理

　           　技术分享

　　所以有inv(b,mod) = pow(b,p-1)

但是当遇到b与mod不互质的情况我们有 ans = a % （mod*b） *b

                技术分享转载自 ：AC-dreamer逆元详解

1-n的逆元

　　设 t1 = mod / i ; t2 = mod % i;

　　所以我们有 t1 * i + t2 = mod

　　即 (t1 * i + t2)  ≡ 0(% mod)

　　移项 - t1 * i ≡ t2(% mod) 

　　同除 i*t2 有 -t1 * inv[t2] ≡ inv[i] & mod

      代入有 inv[i] =  kmod - mod/i * inv[mod % i] % mod ; k 为正整数 且inv[i] > 0

　　为了保证正负 不妨直接写 inv[i] =  （mod - mod/i） * inv[mod % i] % mod ;

应用：组合数逆元 

　　预处理阶乘以及阶乘逆元  转自 ： http://www.cnblogs.com/linyujun/p/5199684.html

技术分享 
 1 const int N = 200000 + 5;
 2 const int MOD = (int)1e9 + 7;
 3 int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 
 4 void init(){
 5     inv[1] = 1;
 6     for(int i = 2; i < N; i ++){
 7         inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
 8     }
 9     F[0] = Finv[0] = 1;
10     for(int i = 1; i < N; i ++){
11         F[i] = F[i-1] * 1ll * i % MOD;
12         Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
13     }
14 }
预处理
技术分享 
1 int C(int n, int m){ 
2     if(m < 0 || m > n) return 0;
3     return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
4 }
公式求组合数

扩展：卢卡斯定理

 C(n, m) % p  =  C(n / p, m / p) * C(n%p, m%p) % p

技术分享 
1 LL Lucas(LL n, LL m, int p){
2         return m ? Lucas(n/p, m/p, p) * C(n%p, m%p, p) % p : 1;
3 }
lucas

 

逆元基本知识


联系
我们