用扩展欧几里德算法求下列乘法逆元，（1）1234mod4321 （2）24140mod40902
答案:4 悬赏:20 手机版
解决时间 2021-04-13 03:07
- 提问者网友：欲劫无渡
- 2021-04-12 13:19
用扩展欧几里德算法求下列乘法逆元，（1）1234mod4321 （2）24140mod40902
最佳答案
- 五星知识达人网友：妄饮晩冬酒
- 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)
存在乘法逆元的前提是：该数与模数互质，否则无解
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)
存在乘法逆元的前提是：该数与模数互质，否则无解
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯