最大公约数
解题思路
我们可以利用辗转相除法来计算最大公约数,这样相对模拟短除更快
如图(计算gcd(27,25)):辗转相除法可以这样用递归重复gcd(a,b) = gcd(b,a % b)来计算
源代码
#include <iostream>
#include <cstdio>
using namespace std;
int gcd(int a,int b)//递归实现辗转相除法
{
if(a % b == 0)return b;
return gcd(b,a % b);
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
int a;
int b;
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}
return 0;
}