欧几里得算法（辗转相除）
题目 最大公约数
思路分析
什么是最大公约数
最大公约数指两个或多个整数共有约数中最大的一个
也称最大公因数、最大公因子，a， b的最大公约数记为（a，b）
同样的，a，b，c的最大 公约数记为（a，b，c）
多个 整数的最大公约数也有同样的记号
求最大公约数有多种 方法 常见的有 质因数分解法 短除法 辗转相除法 更相减损法
辗转相减法求最大公约数
用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。
也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.
要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.
基于上面的原理，就能实现我们的迭代相减法：
(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2
基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值
辗转相减到辗转相除
迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.
即：(a， b) = (a % b， b) = （b, a %b）
相当于每一步都把数字进行缩小 等式右边就是每一步对应的缩小结果
对（a， b）连续使用辗转相除 直到小括号内右边数字为0 小括号内左边的数就是两数最大公约数
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;cin>>T;
while(T--){
int a,b;
cin>>a>>b;
while(b){
int c=a%b;
a=b;
b=c;
}
cout<<a<<endl;
}
return 0;
}
可进行封装
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b, a % b) : a;
}
int main()
{
int T;cin>>T;
while(T--){
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
return 0;
}
库函数_gcd
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;cin>>T;
while(T--){
int a,b;
cin>>a>>b;
cout<<__gcd(a,b)<<endl;
}
return 0;
}
💬 评论