用扩展欧几里德算法求下列乘法逆元，（1）1234mod4321 （2）24140mod40902

答案:4 悬赏:20 手机版

解决时间 2021-04-13 03:07

提问者网友：欲劫无渡
2021-04-12 13:19

最佳答案

五星知识达人网友：妄饮晩冬酒
2021-04-12 14:14

啊一东特农

全部回答

1楼网友：爱难随人意
2021-04-12 16:49

扩展欧几里得算法可以求逆

2楼网友：拜訪者
2021-04-12 15:21

啊一东特农

3楼网友：雪起风沙痕
2021-04-12 15:10

#include
int ans,temp;
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(){
    exgcd(1234,4321,ans,temp);
    ans = (ans % 4321 + 4321) % 4321;
    printf("%d ",ans);
    exgcd(24140,40902,ans,temp);
    ans = (ans % 40902 + 40902) %40902;
    printf("%d ",ans);
    return 0;
}
结果：
1. 3239(正确)
2. 40331(由于24140与40902最大公因数为34,所以扩欧算出来40331*24140 mod 40902=34)
存在乘法逆元的前提是：该数与模数互质，否则无解

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息