逆元

求解一（費(fèi)馬小定理）

$p$是一個(gè)質(zhì)數(shù)，并且$a\%p=0$，則有$a^{p?1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，$a^{p?2}\equiv a^{?1}$，即可得到逆元。

int quic_pow(int a, int n, int mod) {int ans = 1;while(n) {if(n & 1) ans = (ans * a) % mod;a = (a * a) % mod;n >>= 1;}return ans; } int inv(int a, int p) {return quick_pow(a, p - 2, p); }

求解二（拓展歐幾里德）

我們知道拓展歐幾里德算法可以求解$ax+by=gcd(a,b)$，對(duì)逆元考慮假設(shè)有$a?x+b?y=1$那么顯然有$a?x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$，這不就出來(lái)了嗎，$x$就是$a$模$b$下的逆元，當(dāng)然了這里也要有$a,b$互質(zhì)。

int exgcd(int a, int b, int & x, int & y) {if(!b) {x = 1, y = 0;return a;}int gcd = exgcd(b, a % b, x, y);int temp = x;x = y;y = temp - a / b * y;return gcd; } int main() {int a, mod, inv, t;exgcd(a, mod, inv, t);return 0; }

求解三（線性求解逆元）

我們假定有$$mod=k?a+b,k=\frac{mod}{a},b=mod\%a，b<a$$

$$k?a+b\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}mod)$$

同時(shí)乘以$$a^{?1}{b}^{?1}$$

得$$k?b^{?1}+a^{?1}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}mod)$$

$$a^{?1}\equiv ?k?b^{?1}(\mathrm{m}\mathrm{o}\mathrm{d}mod)$$

$$a^{?1}\equiv mod?b^{?1}?k?b^{?1}(\mathrm{m}\mathrm{o}\mathrm{d}mod)$$

所以我們就推導(dǎo)完了。

int inv[n], mod = 100007, n = mod; inv[1] = 1; for(int i = 2; i < n; i++) {inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; }

求解四（$C_n^m$中的逆元求解）

$a{!}^{?1}=n$那么我們不難發(fā)現(xiàn)$(a?1){!}^{?1}=a{!}^{?1}?a$

void init() {fac[0] = 1;for(int i = 1; i < N; i++)fac[i] = (fac[i - 1] * i) % mod;inv[N - 1] = qpow(fac[N - 1], mod - 2);for(int i = N - 2; i >= 0; i--)inv[i] = (inv[i + 1] * (i + 1)) % mod; }

總結(jié)

以上是生活随笔為你收集整理的各种逆元推导的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。