乘法逆元小记

乘法逆元小记

乘法逆元

费马小定理求乘法逆元(O(log(n)))：

ll fast_pow(ll a, ll b, ll mod){ll res = 1;while(b > 0){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
//要求a 与 mod 互质
inline  ll getinv(ll a,ll mod){return fast_pow(a,mod - 2);
}

扩展欧几里得求逆元(O(logn))：

ll exgcd(ll a, ll b,ll &x,ll &y){if(!b){return x = 1, y = 0, a;}ll d = exgcd(b , a % b, x, y);ll t = x;x = y, y = t - (a / b) * y;return d;
}ll get_inv(ll a,ll mod){ll x,y;exgcd(a,mod,x,y);return (x % mod + mod)%mod; //求解最小正逆元
}

线性递推求逆元O(n)：
原理如下：

const int maxn = 1e5 + 10;
void init(int mod){inv[1] = 1;for(int i = 2; i < maxn; ++i){inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;}
}