Tổng chữ số và Ước chung lớn nhất Euclid

Mục tiêu kiến thức

• Áp dụng vòng lặp while để tách các chữ số của một số nguyên lớn mà không phụ thuộc vào chuỗi ký tự.
• Cài đặt thuật toán Euclid tìm ước chung lớn nhất (GCD) với độ phức tạp O(log(min(|a|, |b|))).
• Xử lý các trường hợp số âm và giá trị 0.

Mô tả bài toán

Trong các thuật toán mã hóa khóa công khai (RSA) được giảng dạy tại AI Empire Academy, việc tính toán tổng trọng số chữ số và ước chung lớn nhất giữa hai số nguyên là các thao tác cơ bản thường dùng.

Hãy viết hàm digit_sum_and_gcd(a: int, b: int) -> tuple[int, int, int] thực hiện:

• Tính tổng các chữ số của |a| (lấy giá trị tuyệt đối).
• Tính tổng các chữ số của |b| (lấy giá trị tuyệt đối).
• Tính ước chung lớn nhất gcd(|a|, |b|) bằng thuật toán Euclid.
• Nếu cả hai số đều bằng 0 (a = 0 và b = 0), quy ước gcd(0, 0) = 0.
• Nếu một trong hai số bằng 0, gcd(0, x) = |x|.
• Trả về một tuple gồm đúng 3 số nguyên: (tong_cs_a, tong_cs_b, gcd_ab).

Ràng buộc

• -10¹⁵ ≤ a, b ≤ 10¹⁵.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.