BÀI TẬP 62: TÀU CẬP CẢNG

Một tư nhân có hai tàu thuỷ chuyên vận chuyển hàng khô rất uy tín đối với khách hàng. Được uy tín như vậy là do lịch trình cập cảng của các tàu đảm bảo số ngày quy định, an toàn và cập cảng ngày nào thì cũng rời cảng trong chính ngày đó. Tại cảng chính, tàu thứ nhất cứ K ngày cập cảng 1 lần; tàu thứ hai cứ S ngày cập cảng 1 lần (k≠s).

            Yêu cầu: Lập trình tính xem nếu hai tàu cùng rời cảng thì thời gian ngắn nhất gặp lại nhau tại cảng đó là bao nhiêu ngày?

            - Dữ liệu vào: Đọc từ file văn bản TAU.INP chứa một dòng gồm hai số nguyên dương K và S, hai số cách nhau ít nhất một ký tự trắng.

            - Dữ liệu ra: Kết quả ghi ra file văn bản TAU.OUT thời gian ngắn nhất.

TAU.INP	TAU.OUT
6 4	12

Ý tưởng: Tìm bội chung nhỏ nhất (thuật toán Euclid)

CODE THAM KHẢO:

program Tau_Cap_Cang;

var S,K: integer;

    f: text;

function UCLN(a,b: integer): integer;

var  r: integer;

begin

        while b <> 0 do

        begin

                r:= a mod b;

                a:=b;

                b:=r;

        end;

        UCLN:=a;

end;

begin

        assign(f,'TAU.INP'); reset(f);

        readln(f,K,S);

        close(f);

        assign(f,'TAU.OUT'); rewrite(f);

        write(f,S*K/UCLN(K,S):0:0);

        close(f);

end.