Link Sub: http://www.spoj.com/PTIT/problems/BCGCD/
Người Gửi: Dương Lee
- Problem:
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
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:
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.
Input
2 4 6 9 0 0
Output:
2 4
3 18
- Solution:
UCLN: Áp dụng phép chia lấy dư trong giải thuật Euclid. BCNN: Áp dụng công thức UCLN(a,b) = (a*b)/(BCNN(a,b)) trong giải thuật Euclid.