02/10/2018, 14:02
Ướ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 31 Bộ test kết thúc bởi dòng chứa 2 số 0. Output ...
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
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | 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
