Ướ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á 231

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

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

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *