逆元
同余：
简单来说就是在除法中取模要找到其逆元
逆元：如果一个线性同余方程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 }
只学了这些。。