Hướng dẫn giải của TIN10_LOOP13: Ước chung lớn nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho hai số nguyên N và M, tìm ước chung lớn nhất của hai số đó.
Cách làm
Đầu tiên đổi N và M về số dương (vì số âm vẫn có ước chung giống số dương tương ứng).
Sau đó dùng thuật toán Euclid: lấy số lớn chia cho số nhỏ, lấy số dư. Thay số lớn bằng số nhỏ và số nhỏ bằng số dư, lặp cho đến khi số dư bằng 0 thì số còn lại là ước chung lớn nhất.
#include <bits/stdc++.h>
using namespace std;
int main() {
// N và M có thể âm, nên đổi về số dương trước khi tìm ước chung
long long n, m;
cin >> n >> m;
if (n < 0) n = -n;
if (m < 0) m = -m;
// Thuật toán Euclid: lấy số lớn chia số nhỏ, lặp cho đến khi số dư bằng 0
while (m != 0) {
long long du = n % m;
n = m;
m = du;
}
cout << n << "\n";
return 0;
}
Bình luận