1. 题目

2. 读题（需要重点注意的东西）

思路：

什么是约数？
约数，又称因数。整数a除以整数b(b≠0)，除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

求最大公约数的思路（辗转相除法，又称欧几里得算法）：

a和b的最大公约数等于a模b和b的最大公约数，即：

gcd(a,b) = gcd(b,a%b)

证明如下：

代码思路：
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <iostream>
#include <algorithm>

using namespace std;


int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

可能存在的问题
不理解代码return b ? gcd(b, a % b) : a;
首先要知道a ? b : c是一个三元运算符，如果a中的条件成立，则返回b，否则返回c。
因此在上述代码中，如果a%b为0了，则返回此时的除数b，否则一直进行辗转相除将a模上一个b。

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

求最大公因数的模板题，理解公式并背下代码。