算法思想
假设两个整数为a
和b
,他们的公约数可以表示为gcd(a,b)
。
如果$gcd(a,b) = c$,则必然a = mc
和b = nc
a
除以b
得商和余数,余数r
可以表示为r = a - kb
由$r = a - kb = mc - nck = (m-nk)c$,
知r
是c
的倍数,即c
是r
的约数($r != 0$时)
由于c
是b
的最大公约数,c
又是r
的约数
所以a
和b
的公约数c
也是b
和r
的最大公约数
即$gcd(a,b) = gcd(b,r)$,相当于把较大的一个整数替换一个较小的余数(r = a - kb < a
),
这样不断地迭代,直到余数为0(此时b
为上次的余数,即最大公约数)
#include <iostream>
using namespace std;
//欧几里得辗转相除法递归写法
int gcd1(int a, int b)
{
if (a % b == 0) return b;
else return gcd1(b, a % b);
}
//欧几里得辗转相除法非递归写法
int gcd2(int a, int b)
{
int tmp;
while (b)
{
tmp = a;
a = b;
b = tmp % b;
}
return a;
}
//y总写法
int gcd3(int a, int b)
{
return b ? gcd3(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int a, b;
cin >> a >> b;
cout << gcd3(a, b) << endl;
}
}