3
12 8
25 10
21 63

4
5
21

解法1：暴力，超时

算法：最容易想到的暴力法，从 a,b  两个数中的较小数开始向下逐步试探能否同时整除两个数，可以就得到答案，时间复杂度 O(max(a, b)) 结果超时。

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>   
#include <vector>

int min(int a, int b) { return a < b ? a : b; }

int main()
{
    int n, a, b, s, m;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &a, &b);
        s = 1, m = min(a, b);
        for (int i = m; i >= 1; --i)
        {
            if (a % i == 0 && b % i == 0) {
                s = i; break;
            }
        }
        printf("%d\n", s);
    }
    return 0;
}

解法2：辗转相除法

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>  

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int main()
{
    int n, a, b, big, small, f=0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &a, &b);
        big = max(a, b);
        small = min(a, b);
        while (small)
        {
            f = small;
            a == big ? a %= small : b %= small;
            big = max(a, b);
            small = min(a, b);
        }
        printf("%d\n", f);
    }
    return 0;
}

解法3：更相减损术

算法：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。 —— 《九章算术》

该算法原本是为约分而设计的，就是用来给分子分母同时约分，约到最简分数，也可以用来求任意两个数的最大公约数。

翻译：

第一步：有两个数 a,b 现在要将其约到最简，如果 a, b 可以整除 2 就都约去 2，如果 a, b  均和 2 互质，执行第二步

第二步：分子分母两数做差，大的减掉小的，如果减完分子分母不相等，重复第二步，否则进入第三步

第三步：使用第二步中相减为零的两个被减数和减数，用其中一个对原来的分子分母进行约分，算法结束

图示：以题目数据 21 63 为例

 AC:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>  

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int main()
{
    int n, a, b, big, small, f;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &a, &b);
        f = 1;
        while (!(a & 1) && !(b & 1)) a >>= 1, b >>= 1, f <<= 1;
        big = max(a, b);
        small = min(a, b);
        while (big != small)
        {
            a == big ? a -= b : b -= a;
            big = max(a, b);
            small = min(a, b);
        }
        printf("%d\n", small * f);
    }
    return 0;
}