文章目錄

• • • 1 什么是逆元
    • 2 存在逆元的條件是什么
    • 3 怎樣求一個(gè)數(shù)的逆元
    • • 1.[ 歐幾里得擴(kuò)展]
      • 2. 費(fèi)馬小定理 （最常用）
    • 4 擴(kuò)展（常用）
    • • 1. 線性逆元（常用）
      • 2 快速階乘逆元（常用）

逆元是數(shù)論之中的一個(gè)重要概念
參考博客 ACdreamer
參考書籍 《高中數(shù)學(xué) 選修 4-6》

1 什么是逆元

2 存在逆元的條件是什么

3 怎樣求一個(gè)數(shù)的逆元

1.[ 歐幾里得擴(kuò)展]

不懂的點(diǎn)這里
$a?b+n?t=1$

long long ex_gcd(long long a,long long b,long long &x,long long &y) {if(b == 0){x = 1;y = 0;return a;}long long m = ex_gcd(b,a%b,y,x);y -= a/b * x;return m; } int main() {long long a,b,x,y;cin>>a>>b; //求a 關(guān)于b的逆元if(ex_gcd(a,b,x,y)==1)cout<<(x%b+b)%b<<endl;elsecout<<"None"<<endl;return 0; }

2. 費(fèi)馬小定理 （最常用）

• 如果n 是素?cái)?shù)，費(fèi)馬小定理 $a^{(n?1)}=1(modn)$,那么a關(guān)于n的逆元就 是$a^{(n?2)}$

long long qpow(long long a,long long b,long long m)//快速冪 {long long ans = 1;a %= m;while(b > 0){if(b & 1)ans = (ans * a) % m;a = a * a % m;b >>= 1;}return ans; } long long Fermat(long long a,long long p)//前提p是質(zhì)數(shù) {return qpow(a,p-2,p); }

• 如果n 不是素?cái)?shù)，利用歐拉定理同理

long long Euler(long long n)//求一個(gè)數(shù)的歐拉值 {if(n == 1)return 1;long long ans = n;for(int i = 2;i * i <= n; ++i){if(n % i== 0){while(n % i == 0)n /= i;ans = ans/i * (i-1);}}if(n != 1)ans = ans/n*(n-1);return ans;} long long Euler_to_invers(long long a,long long b)// {return qpow(a,Euler(b)-1,b); }

4 擴(kuò)展（常用）

1. 線性逆元（常用）

如果p是一個(gè)奇質(zhì)數(shù)，則可以在o(n）時(shí)間內(nèi)求出所有關(guān)于同余系關(guān)于p的逆元
證明如下
對p進(jìn)行帶余除法，求i的逆元
$p=i?k+t(0<t<i)$
等式兩邊同時(shí)對關(guān)于p取模
于是 $t=?i?k(modp)$
等式兩邊同時(shí)乘以 $inv(i)?inv(t)$
$inv(i)=?k?inv(t)(modp)$
$inv(i)=(p?k?inv(t))(modp)$
$inv(i)=(p?p/i?inv(p\%i))(modp)$
這樣就可以用一個(gè)數(shù)組存儲關(guān)于p的所有逆元

int inv[10000];int p;cin>>p;inv[1] = 1;for(int i = 2;i < p; ++i){inv[i] = (p - p/i*inv[p%i]%p)%p;}for(int i = 1;i < p; ++i)cout<<inv[i]<<" ";cout<<endl;for(int i = 1;i < p; ++i)cout<<i * inv[i] % p<<" ";

2 快速階乘逆元（常用）

const int maxn = 1e5+10; long long fac[maxn],invfac[maxn]; void init(int n){fac[0] = 1;for(int i = 1;i <= n; ++i) fac[i] = fac[i-1]*i%mod;invfac[n] = qpow(fac[n],mod-2);for(int i = n-1;i >= 0; --i) invfac[i] = invfac[i+1]*(i+1)%mod; }

總結(jié)

以上是生活随笔為你收集整理的数论逆元的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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