Ước số chung lớn nhất

Đề bài

Trả về ước số chung lớn nhất của a và b. Thuật toán Euclid lặp lại việc thay thế (a, b) bằng (b, a mod b) cho đến khi b bằng 0.

Cài đặt hàm gcd(a, b).

a: Số thứ nhất. b: Số thứ hai.

Trả về gcd(a, b). gcd(0, 0) là 0.

0 ≤ a, b ≤ 10¹⁸

Ví dụ 1

Đầu vào:
a = 48
b = 18

Kết quả mong đợi:
expected = 6

Đầu vào:
long long a = 48;
long long b = 18;

Kết quả mong đợi:
long long expected = 6;

Đầu vào:
long a = 48;
long b = 18;

Kết quả mong đợi:
long expected = 6;

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, nên kết quả là 6.

Ví dụ 2

Đầu vào:
a = 17
b = 5

Kết quả mong đợi:
expected = 1

Đầu vào:
long long a = 17;
long long b = 5;

Kết quả mong đợi:
long long expected = 1;

Đầu vào:
long a = 17;
long b = 5;

Kết quả mong đợi:
long expected = 1;

17 và 5 không có ước chung nào ngoài 1.

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

gcd không đổi khi bạn thay một cặp bằng bước lấy phần dư.

Gợi ý 2

Tiếp tục đổi vai trò của hai số cho đến khi số thứ hai bằng 0.

Gợi ý 3

Nhớ xử lý trường hợp cả hai đầu vào đều bằng 0.

Độ phức tạp mong đợi

thời gian O(log min(a, b)), bộ nhớ phụ O(1)

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.