简介

Coddy 数学谜题课程的第 10 课，共 20 课。

两个正整数 x 和 y 的最大公约数（GCD）是 x 和 y 的最大公因数。

例如，

GCD(6, 15) = 3
GCD(7, 13) = 1
GCD(18, 30) = 6

最大公约数也可以定义为三个或更多正整数的最大公因数，即它们共有的最大因数。最大公约数为 1 的两个或更多正整数称为彼此互质。[Weisstein, Eric W. “Greatest Common Divisor.” 摘自 MathWorld，Wolfram 网络资源。https://mathworld.wolfram.com/GreatestCommonDivisor.html]

用欧几里得算法求 GCD

欧几里得提出的求最大公约数的方法基于这样一个事实：给定两个正整数 x 和 y，且 y > x，x 和 y 的公因数与 y - x 和 x 的公因数相同。

因此，欧几里得的求最大公约数方法是用两个数的差替换较大的数，并重复这一过程，直到两个数相等：此时它们的值就是最大公约数。

示例：GCD(6, 15) = GCD(6, 15 - 6) = GCD(6, 9) = GCD(6, 9 - 6) = GCD(6, 3) = GCD(6 - 3, 3) = GCD(3, 3) = 3

挑战

简单

编写 Python 代码 gcd，接收一个包含两个整数的向量 v，并求出这两个给定数字的最大公约数。

请注意，v[0] <= v[1]。

亲手试试

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int v[4096];
    int vn = 0;
    char line[65536];
    if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
    char* tok = strtok(line, " \t\r\n");
    while (tok) { v[vn++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int r = gcd(v, vn);
    printf("%d\n", r);
    return 0;
}