题目描述

求两个正整数 m 和 n 的最大公约数

• 最大公约数是指能够同时整除 m 和 n 的最大正整数，记为 gcd(m, n)
• 比如: gcd(8, 6) = 2, 因为 8 % 2 = 0, 6 % 2 = 0
• 并且不存在一个大于 2 的数能同时整除 8 和 6

请用递归函数实现

int gcd(int x, int y) {
    // 第一步: 递归函数先写终止条件

    // 第二步: 将问题分解成几个小问题
}

输入格式

给定的m, n（$1 \lt m, n \le 2*10^9$)

输出格式

输出 m 和 n 的公约数

8 4

4

提示

• 设 $gcd(n, m) = d$
• 设 n 和 m 做除法, $n=p \times m+q$, p 是商, q 是余数
• 由于 n 是 d 的倍数, $p \times m$ 也是 d 的倍数, 所以余数 q 也是 d 的倍数
• 那么 gcd(m, q) = d
• 举个例子
  • gcd(8, 6) = gcd(6, 8 % 6) = gcd(6, 2) = gcd(2, 6 % 2) = gcd(2, 0) = 2
• 那么，我们可以实现递归函数

// 用递归函数求最大公约数
int gcd(int x, int y) {
    // 第一步: 递归函数先写终止条件
    if (y == 0) return x;

    // 第二步: 将问题分解成几个小问题
    return gcd(y, x % y);
}

• 下面的写法更简洁

// 用递归函数求最大公约数
int gcd(int x, int y) {
    // 如果 y != 0, 就返回 gcd(y, x % y)
    // 如果 y == 0, 就返回 x
    return y ? gcd(y, x % y) : x;
}

• 还有更更简洁的写法

// 直接使用 __gcd() 函数
cout << __gcd(x, y) << '\n';

数据规模与限制

• 1s, 1024KiB for each test case.