成人午夜在线观看日韩,亚洲综合成人av在线,中文字幕人妻不卡精品

定義，求法，用途，例題較少

也挺簡單

定義：

若 \(a,m\) 互質，且滿足：

\[a\times x\equiv 1 \pmod{m} \]

則稱 \(x\) 是 \(a\) 在 \(\bmod b\) 意義下的乘法逆元，也記為 \(a^{-1}\)。

用途：

主要用于 \(\frac{x}{y} \bmod m\) 求值，一般是因為無法化簡（例如數太大。

求法：

1. \(exgcd\):

\[ax\equiv 1 \pmod{m} \]

轉化得：

\[ax+my=1 \]

運用 \(exgcd\) 求解即可。

CODE（點擊查看）

void exgcd(int a,int b,int &x,int &y){
	if(b==0) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
	int a,m; scanf("%d%d",&a,&m);
	int x,y;
	exgcd(a,m,x,y);
	printf("%d",(x%m+m)%m); //注意x的取值范圍。 
}

2.費馬小定理（m是質數）：

費馬小定理

我們將費馬小定理帶入原式，得：

\[ax\equiv a^{m-1} \pmod{m} \]

\[x\equiv a^{m-1} \div a \pmod{m} \]

\[x \equiv a^{m-2} \pmod{m} \]

所以我們只需求 \(a^{m-2}\) 即可，用快速冪。

COED（點擊查看）

inline int fpow(int a,int b,int mod){
	int ans=1;
	while(b){
		if(b&1) ans=a*ans%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
int main(){
	int a,m; scanf("%d%d",&a,&m);
	printf("%d",fpow(a,m-2,m));
}

3.線性求法（求得 \(1 \text{ ~ } n\) ）：

這種方法在但求一個時慢于前兩種，但求 \(1 \text{ 到 } n\) 是優于前兩種例題。
設 \(m=k \times a+r (1 \le r < a < m)\)
于是有：

\[ka+r \equiv 0 \pmod{m} \]

乘上 \(r^{-1},a^{-1}\) ，得：

\[kr^{-1}+a^{-1}\equiv 0 \pmod{m} \]

\[a^{-1}\equiv -kr^{-1} \pmod{m} \]

\[a^{-1}\equiv -\left\lfloor\dfrac{m}{a}\right\rfloor\times(m \bmod a)^{-1} \pmod{m} \]

我們又知道，\(1^{-1}\) 為 \(1\) 于是就可以線性推了。

CODE（例題，點擊查看）

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
long long n,p,inv[N];

template<typename T>
inline void read(T &x){
    char s=getchar();x=0;bool pd=false;
    while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
    while('0'<=s&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
    if(pd) x=-x;
}

int main(){
	read(n),read(p);
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(p-p/i)*inv[p%i]%p;
	for(int i=1;i<=n;i++)
		printf("%lld\n",inv[i]);
}

CODE（主要代碼，點擊查看）

inv[1]=1;
for(int i=2;i<=n;i++)
	inv[i]=(p-p/i)*inv[p%i]%p;

4.階乘求逆元：

求：\(1! \text{ 到 } n!\) 的逆元。
給出一個式子，其中 \(v(i)\) 表示 \(i\) 的逆元。

\[v((i-1)!)=\frac{1}{(i-1)!}=\frac{1}{i!}*i=v(i!)*i \]

于是乎又可以線性推了。

然而這種做法還可以求 \(l \text{ 到 } r\) 的逆元。
具體的：

\[v(i)=\frac{1}{i}=\frac{1}{i!}\times(i-1)!=v(i!)\times(i-1)! \]

然后可求。

附：有趣的題：

給定一個長度為 \(n\) 的序列 \(a\) ，求 \(a_1 \text{ 到 } a_n\) 所有數的乘法逆元。
\(1 \le n \le 5e6\) （要求復雜度 \(\operatorname{O} n\)）
做法：
先維護前綴積 \(q_i\)
通過：

\[q_i^{-1}\times a_i=\frac{1}{\prod\limits_{j=1}^ia_j}\times a_i=q_{i-1}^{-1} \]

推得 \(q^{-1}\) 的值。
然后通過：

\[q_i^{-1}\times q_{i-1}=\frac{1}{\prod\limits_{j=1}^ia_j}\times\prod\limits_{j=1}^{i-1}a_j=a_i^{-1} \]

得解。

參考 http://www.rzrgm.cn/zjp-shadow/p/7773566.html

本文來自博客園，作者：xrlong，轉載請注明原文鏈接：http://www.rzrgm.cn/xrlong/articles/17072952.html

xrlong

博客密碼是 K8 色號

乘法逆元

定義：

用途：

求法：

1. \(exgcd\):

2.費馬小定理（m是質數）：

3.線性求法（求得 \(1 \text{ ~ } n\) ）：

4.階乘求逆元：

附：有趣的題：

公告

Loading