题目描述

给定n对正整数$a_i$,$b_i$，请你求出每对数的最大公约数。

解题思路

(1)最大公约数
最大公约数指两个或多个整数中公共约数中最大的一个,也称最大公因数、最大公因子。
a,b的最大公约数记为（a，b),同样的，a,b,c的最大公约数记为（a,b,c),多个 整数的最大公约数也有同样的记号。
(2)辗转相除法
(a,b) = (a%b,b) = （b,a%b); (a,b)=（b,a%b）【常用形式】
相当于每一步都把数字进行缩小，等式右边就是每一步对应的缩小结果。
对(a,b)连续使用辗转相除，直到小括号内右边数字为0，小括号内左边的数就是两数最大公约数。

举例说明
(78，14)=(14，78%14=8)=(14,8), (14,8)=(8,14%8=6)=(8,6),(8,6)=(8,8%6=2)=(8,2)
(8,2)=(2,8%2=0)=(2,0) 所以(78,14)=(2,0),78和14的最大公约数为2

(45,27)=(27,45%27=18)=(27,18), (27,18)=(18,27%18=9)=(18,9),(18,9)=(9,18%9=0)=(9,0)
所以(45,27)=(9,0),45和27的最大公约数为9

(3) $d | a$ (‘|’表示整除符合，即a可以被d整除) 等价于 $\frac{a}{d}$,a%d=0
如果 $d | a$ 和 $d | b$ ,则 $d | ax+by$

辗转相除法

C++ 代码

#include<iostream>

using namespace std;


int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
    /*三目运算符
    if(!b) return a;   
    else return gcd(b,a%b);
    */
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",gcd(a,b));
    }
    return 0;
}