当前位置: 代码迷 >> 综合 >> 扩展扩展欧几里得算法求逆元
  详细解决方案

扩展扩展欧几里得算法求逆元

热度:19   发布时间:2024-01-15 07:58:27.0

若a*x≡1(mod b) ,a,b互质,则称x为a的逆元。

根据逆元的定义,则可以转化为a*x+b*y=1。这样就可以用扩展欧几里得算法求x了。

注意:在gcd不为1说明逆元不存在(因为c=1,c%gcd==0为有整数解的充分必要条件),若为1,调整x0到0~m-1的范围中即可


int ex_gcd(int a,int b,int &x,int &y)       //扩展欧几里得 
{if(b==0){x=1;y=0;return a;}int r=ex_gcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return r;
}
int mod_reverse(int a,int b)//a*x=1(mod b) 求a的逆元x 
{int d,x,y;d=ex_gcd(a,b,x,y);if(d==1)return (x%b+b)%b;elsereturn -1;
}