欧几里得算法和扩展的欧几里得算法
欧几里得算法和扩展的欧几里得算法
最新推荐文章于 2024-11-28 23:42:47 发布

谭墨墨快乐 于 2012-04-26 14:40:42 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
欧几里得算法又称辗转相除法
给定两个正整数m,n。求他们的最大公约数,算法代码为
#include "stdafx.h"
#include<iostream>
using namespace std;
int gcd(int m,int n)
{
int r=n%m;
while(r!=0)
{
n=m;
m=r;
r=n%m;
}
return m;
}
int _tmain(int argc, _TCHAR* argv[])
{
int m,n;
cin>>m>>n;
if(m>n)
{
int temp=m;
m=n;
n=temp;
}
int h=gcd(m,n);
cout<<"最大公约数是"<<h<<endl;
cout<<"最小公倍数是:"<<(m*n)/gcd(m,n)<<endl;
return 0;
}
扩展的欧几里得算法是:
给定两个整数m、n,我们计算它们的最大公约数d和两个整数a和b,使得am+bn=d
算法代码如下
#include "stdafx.h"
#include<iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int m,n,a1,b,a,b1,c,d,q,r,t;
a1=b=1;
a=b1=0;
cin>>m>>n;
c=m;
d=n;
q=c/d;
r=c%d;
while(r!=0)
{
c=d;
d=r;
t=a1;
a1=a;
a=t-q*a;
t=b1;
b1=b;
b=t-q*b;
q=c/d;
r=c%d;
}
cout<<d<<endl;
cout<<a<<" "<<b<<endl;
return 0;
}
相关知识
Sylius:如何扩展Taxon模型?
团花树形成层扩展蛋白基因cDNA的克隆和序列分析
植物抗病性是植物避免、阻止病原物侵入与扩展、减轻发病和降低损失程度的特性。()
兰花种植的繁殖技巧,两步快速扩展建兰园,不愁花苗没来源
花小钱办大事 剑灵会员扩展服务性价比
鲜切百合花可以拿去晒太阳吗(扩展资料:)
首都花卉布置方案发布:国庆花坛摆放范围扩展至三环
野生动植物栖息地不断扩展优化 旗舰物种野生种群持续增长
全方位国风美妆品牌矩阵——朵芬泉携手彩妆产品扩展护肤体验
【农业科技】如何理解农业元宇宙?没搞懂就是一场伪命题
原文链接: 欧几里得算法和扩展的欧几里得算法 https://www.huajiangbk.com/newsview776086.html
| 上一篇: 西游记红孩儿是哪一集 | 下一篇: 瘦西湖“二分明月忆扬州”大型沉浸... |





