Giới thiệu

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

Bội chung nhỏ nhất của hai số nguyên x và y, thường được ký hiệu là LCM(x,y), là số nguyên dương nhỏ nhất chia hết cho cả x và y.

Ví dụ:

LCM(24, 16) = 48
LCM(3, 5) = 15
LCM(4, 6) = 12.

Nó được dùng để cộng các phân số.

Ví dụ: 7/24+5/16 = 7 * (2/48) + 5 * (3/48) = (14+15) / 48 = 29/48.

Nó được dùng để tìm thời điểm những người có chu kỳ cụ thể sẽ gặp lại nhau. Ví dụ: Dan đi uống bia vào mỗi đêm thứ ba, còn John vào mỗi đêm thứ tư. Vì vậy, họ sẽ gặp nhau cứ sau 12 đêm.

Nó có liên hệ với ước chung lớn nhất qua công thức:

LCM(x, y) = (x * y) / GCD(x, y)

Thử thách

Dễ

Viết một hàm calcLCM nhận một vector gồm hai số nguyên, v, rồi tính số nhỏ nhất chia hết cho cả hai số.

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 = calcLCM(v, vn);
    printf("%d\n", r);
    return 0;
}