用扩展的欧几里德算法求最大公约数以及逆元
#include
void exgcd(int d,int f)
{
int x1,x2,x3,y1,y2,y3,q,t1,t2,t3;
x1=1;
x2=0;
x3=f;
y1=0;
y2=1;
y3=d;
while(y3>0)
{
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;
【用扩展的欧几里德算法求最大公约数以及逆元】if(y3==1)
{
printf("%d和%d互素 逆元是%d/n/n",d,f,y2);
break;
}
}
if(y3==0)
{
printf("%d和%d无逆元,他们的最大公约数是%d/n/n",d,f,x3);
}
}
void main()
{
int a,b;
printf("/n用扩展的欧几里德算法求最大公约数以及逆元/n");
printf("/n请输入两个整数：/n");
scanf("%d %d",&a,&b);
exgcd(a,b);
}
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- Docker应用:容器间通信与Mariadb数据库主从复制