题目描述
题目要求:给n对数,求出n对数的最大公约数
辗转相除法:1.若d|a,d|b,则d|(xa+yb);
2.a mod b = a-cb;
3.gcd(a,b)=gcd(b,a-cb);
C++ 代码
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
return b ? gcd(b,a%b):a;//当b不为0时,继续求;直到为0的时候返回a的值;不用担心比较a,b的大小,a%b永远小于b,即在调用函数后后项值一定是较小值。
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}
return 0;
}