Hướng dẫn giải

Cho hai số nguyên ~N~ và ~M~ với ~|N|, |M| \le 10^9~, tìm ước chung lớn nhất của hai số đó.

Cách làm

Trước hết đổi hai số về dương, vì ước chung lớn nhất luôn không âm. Ví dụ với ~-36~ và ~-81~ thì ta tính với ~36~ và ~81~.

Sau đó dùng thuật toán Euclid: lấy số lớn chia cho số nhỏ để có số dư ~r~, rồi thay số lớn bằng số nhỏ và số nhỏ bằng ~r~. Lặp lại cho đến khi số nhỏ bằng 0, khi đó số còn lại chính là ước chung lớn nhất.

Nên dùng kiểu ~long long~ để chắc chắn không tràn số.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    // Ước chung lớn nhất không âm, nên đổi hai số về dương trước
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    // Thuật toán Euclid: lấy số lớn chia số nhỏ, rồi lặp lại với số dư
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    cout << a << "\n";
    return 0;
}