首页 > 代码库 > 乘法逆元

乘法逆元

2024-11-14 14:15:02   202人阅读

定义：当(a,p)=1时，存在ax≡1(mod p)，则x叫作a在模p意义下的乘法逆元。

求法：

1.当p为质数时，由费马小定理，得ap-1≡1(mod p)，即(a·ap-2)≡1(mod p)，则a在模p意义下的乘法逆元是ap-2，直接用快速幂可求得。

2.当p不为质数时，用扩展欧几里得算法求a的逆元。

代码：

 1 int exgcd(int a,int b,int &x, int &y)
 2 {
 3     int d=a;
 4     if(b!=0){
 5         d=exgcd(b,a%b,y,x);
 6         y-=(a/b)*x;
 7     }
 8     else{
 9         x=1;
10         y=0;
11     }
12     return d;
13 }
14 int mod_inverse(int a,int p)
15 {
16     int x, y;
17     int d=exgcd(a,p,x,y);
18     return (p+x%p)%p;
19 }

 应用：计算(a/b)%p时，（比如求组合数取模），可以转化为a*c%p，其中c是b在模p意义下的乘法逆元。

乘法逆元


联系
我们