逆元

同余：

简单来说就是在除法中取模要找到其逆元

逆元：如果一个线性同余方程ax ≡ 1( mod b)，则x称为a mod b的逆元

简单来说就是mod b是一种环境，而所求的x是a在mod b环境中的倒数

以下是求逆元的法子

• 扩展欧几里得法求逆元，时间复杂度o(logn)

1 void exgcd(int a, int b, int& x, int& y) {
2   if (b == 0) {
3     x = 1, y = 0;
4     return;
5   }
6   exgcd(b, a % b, y, x);
7   y -= a / b * x;
8 }

• 欧拉定理

若a和b互质，则有 a^(φ(b))≡1(mod b),其中φ(b)为欧拉函数

所以a^(φ(b)-1)为a在mod b环境下的逆元

 1 int qpow(int a,int b,int mod){
 2     int ans=1,res=a%mod;
 3     while(b){
 4         if(b&1)    ans=ans*res%mod;
 5         res=res*res%mod;
 6         b>>=1;
 7     }
 8     return ans%mod;
 9 }
10 int inv(int a,int mod){
11     return qpow(a,φ(b)-1,mod)%mod;
12 }

• 费马小定理

若b为素数，则存在a^(b-1)≡1(mod b)

公式与欧拉定理类似

 1 int qpow(int a,int b,int mod){
 2     int ans=1,res=a%mod;
 3     while(b){
 4         if(b&1)    ans=ans*res%mod;
 5         res=res*res%mod;
 6         b>>=1;
 7     }
 8     return ans%mod;
 9 }
10 int inv(int a,int mod){
11     return qpow(a,mod-2,mod)%mod;
12 }

• 线性求逆元

当所求的逆元有很多的时候，可能会t，线性复杂度o(n)

1 inv[1] = 1;
2 for (int i = 2; i <= n; ++i) {
3   inv[i] = (long long)(mod - mod / i) * inv[mod % i] % p;
4 }

只学了这些。。