$\color{green}{<–画图不易,点下这里赞一下吧}$
什么是最大公约数
最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子,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 <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int a, b;
cin >> a >> b;
//辗转相除,直到小括号内右边数为0
while(b)
{
//c 一定小于 b
int c = a % b;
//小括号左边放除数,右边放约数
a = b;
b = c;
}
//小括号内左边数为最大公约数
cout << a << endl;
}
}
聊胜于无的优化
对于(a, b),如果 a % b == 0, 则b就是最大公约数,可以提前结束循环。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int a, b;
cin >> a >> b;
//a % b == 0, 则b就是最大公约数,可以提前结束循环。
while(a % b)
{
int c = a % b;
a = b;
b = c;
}
cout << b << endl;
}
}
or2
好翘!
orz
翘到能顶起一瓶汽水!
死去的梗又开始攻击我忠实粉丝
时间复杂度是多少
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int a[N];
int n;
int main(){
cin>>n;
while(n–){
int a,b;
cin>>a>>b;
cout<<__gcd(a,b)<<endl;
}
return 0;
}
orz
海绵宝宝不仅蟹黄包做得好吃,题解也写得很好
懂了懂了,海绵宝宝yybs😘
永远不死
这就是海绵宝宝
第一次彻底学懂辗转相除法!!!
or2为什么scanf和cin的时间相差那么大,scanf200ms,cin1000多ms
orz
orz
海绵宝宝太懂我了