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. 总结

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