Ước chung lớn nhất, bội chung nhỏ nhất (Cơ bản)

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCGCD/

1. Đề bài euclid tìm ước chung lớn nhất, bội chung nhỏ nhất

Tìm UCLN và BCNN của 2 số.

Input

Gồm nhiều test, mỗi test trên 1 dòng chứa 2 số nguyên dương không quá 2³¹

Bộ test kết thúc bởi dòng chứa 2 số 0.

Output

Mỗi test xuất ra trên 1 dòng chứa 2 số cách nhau bởi dấu cách lần lượt là UCLN và BCNN.

Example

Input:
2 4
6 9
0 0

Output:
2 4
3 18

Hướng dẫn 

– áp dụng thuật toán euclid. BCNN của 2 số a, b sẽ bằng a*b chia cho UCLN(a,b)

Thuật toán euclid tìm ước chung lớn nhất, bội chung nhỏ nhất

2. Code euclid tìm ước chung lớn nhất, bội chung nhỏ nhất

const   fi='';
var
        f:text;
        n,m:int64;

procedure xuli(a,b:int64);
var     r:int64;
begin
        while a mod b <>0 do
                begin
                        r:=a mod b;
                        a:=b;
                        b:=r;
                end;
        writeln(b, ' ', (m*n) div b);
end;

begin
	assign(f,fi); reset(f);
        repeat
                readln(f,m,n);
                if (m=n) and (m=0) then
                        begin
                        	close(f);
                                exit;
                        end;
                xuli(m,n);
        until 1=2;
end.

Từ khóa:

• code pascal Ước chung lớn nhất, bội chung nhỏ nhất
• BCGCD spoj PTIT