Giới thiệu

Bài học 10 trên 20 trong khóa học Câu đố toán học của Coddy.

Ước chung lớn nhất (GCD) của hai số nguyên dương x và y là ước số lớn nhất chung của x và y.

Ví dụ:

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

Ta cũng có thể định nghĩa ước chung lớn nhất của ba hoặc nhiều số nguyên dương là ước số lớn nhất chia hết cho tất cả các số đó. Hai hoặc nhiều số nguyên dương có ước chung lớn nhất bằng 1 được gọi là nguyên tố cùng nhau. [Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Thuật toán Euclid tìm GCD

Phương pháp Euclid dùng để tính ước chung lớn nhất dựa trên thực tế rằng, với hai số nguyên dương x và y sao cho y > x, các ước chung của x và y cũng chính là các ước chung của y - x và x.

Vì vậy, phương pháp Euclid tính ước chung lớn nhất của hai số nguyên dương bằng cách thay số lớn hơn bằng hiệu của hai số, rồi lặp lại quá trình này cho đến khi hai số bằng nhau. Giá trị đó chính là ước chung lớn nhất của chúng.

Ví dụ: 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

Thử thách

Dễ

Viết code Python, gcd, nhận một vector gồm hai số nguyên, v, và tìm GCD của hai số đã cho.

Lưu ý rằng v[0] <= v[1].

Tự làm thử

#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;
}