Introduction

Coddyの「数学パズル」コースのレッスン 10/20。

2つの正の整数xとyの最大公約数（GCD）は、xとyに共通する最大の約数です。

例えば、

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

最大公約数は、3つ以上の正の整数に対しても、それらすべてに共通する最大の約数として定義できます。最大公約数が1である2つ以上の正の整数は、互いに素であると言われます。[Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

GCDを求めるためのユークリッドの互除法

最大公約数を計算するためにユークリッドによって導入された手法は、y > x である2つの正の整数xとyが与えられたとき、xとyの公約数は y - x と x の公約数と同じであるという事実に基づいています。

したがって、2つの正の整数の最大公約数を計算するユークリッドの手法は、大きい方の数値を数値の差で置き換え、2つの数値が等しくなるまでこれを繰り返すことで構成されます。その等しくなった数値が最大公約数です。

例: 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

チャレンジ

簡単

2つの整数のベクトル v を受け取り、それら2つの数値の最大公約数（GCD）を求めるPythonコード gcd を記述してください。

なお、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;
}