用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b,n,求出a。请编译运行通过,谢谢啦
答案:2 悬赏:80
解决时间 2021-02-18 22:04
- 提问者网友:你给我的爱
- 2021-02-18 08:59
用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b,n,求出a。请编译运行通过,谢谢啦
最佳答案
- 二级知识专家网友:一把行者刀
- 2021-02-18 10:16
#include
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("输入两个数:\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素,乘法的逆元是:%d\n",b,n,z);
else
printf("%d和%d不互素,最大公约数为:%d\n",b,n,z);
return 0;
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = ( f>=d )?f:d;
y3 = ( f>=d )?d:f;
while( 1 )
{
if ( y3 == 0 )
{
*result = x3;
return 0;
}
if ( y3 == 1 )
{
*result = y2;
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("输入两个数:\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素,乘法的逆元是:%d\n",b,n,z);
else
printf("%d和%d不互素,最大公约数为:%d\n",b,n,z);
return 0;
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = ( f>=d )?f:d;
y3 = ( f>=d )?d:f;
while( 1 )
{
if ( y3 == 0 )
{
*result = x3;
return 0;
}
if ( y3 == 1 )
{
*result = y2;
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
全部回答
- 1楼网友:一秋
- 2021-02-18 11:49
引用有钱买不起房子的回答:
#include <stdio.h>
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("输入两个数:\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素,乘法的逆元是:%d\n",b,n,z);
else
printf("%d和%d不互素,最大公约数为:%d\n",b,n,z);
return 0;
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = ( f>=d )?f:d;
y3 = ( f>=d )?d:f;
while( 1 )
{
if ( y3 == 0 )
{
*result = x3;
return 0;
}
if ( y3 == 1 )
{
*result = y2;
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
这是一个错误的算法啊
#include <stdio.h>
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("输入两个数:\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素,乘法的逆元是:%d\n",b,n,z);
else
printf("%d和%d不互素,最大公约数为:%d\n",b,n,z);
return 0;
}
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
x3 = ( f>=d )?f:d;
y3 = ( f>=d )?d:f;
while( 1 )
{
if ( y3 == 0 )
{
*result = x3;
return 0;
}
if ( y3 == 1 )
{
*result = y2;
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
这是一个错误的算法啊
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯