最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

乘法逆元

来源:博客园

也挺简单


(相关资料图)

定义:

若 \(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是质数):

费马小定理:当 \(m\) 是质数,且 \(a,m\) 互质时,有:

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

证明:由欧拉定理可得:

\[a^{\phi(m)}\equiv 1 \pmod{m}\]\[\because m \text{ 是质数}\]\[\therefore \phi(m)=m-1\]\[\therefore a^{m-1}\equiv 1 \pmod{m} \text{ ,证毕}\]

我们将这个式子带入原式,得:

\[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(例题,点击查看)
#includeusing namespace std;const int N=3e6+5;long long n,p,inv[N];templateinline void read(T &x){    char s=getchar();x=0;bool pd=false;    while(s<"0"||"9"
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)!\]

然后可求。

参考 https://www.cnblogs.com/zjp-shadow/p/7773566.html

关键词: 点击查看 主要用于 也挺简单