Thuật toán nhân Karatsuba chia mỗi số (theo cơ số 10) làm đôi và đệ quy thực hiện 3 phép nhân con. Quy ước cài đặt: nếu một trong hai toán hạng có 1 chữ số (theo số chữ số lớn nhất của hai số) thì thực hiện 1 phép nhân cơ bản (đếm là 1) và dừng đệ quy; ngược lại tách mỗi số làm hai nửa với điểm chia m = ceil(d/2) (d là số chữ số lớn nhất) và gọi đệ quy đúng 3 lần trên các nửa.
Cho hai số nguyên không âm a, b, hãy đếm tổng số phép nhân cơ bản (các lần chạm đáy) khi nhân chúng bằng Karatsuba theo quy ước trên.
a = 12, b = 34: d = 2 nên tách thành 3 lời gọi con, mỗi con có toán hạng 1 chữ số → mỗi con đếm 1 → tổng 3.
Một dòng chứa hai số nguyên không âm a và b cách nhau bởi dấu cách.
0 ≤ a, b < 10^18.
Một dòng: tổng số phép nhân cơ bản.
Ví dụ:
Đầu vào:
12 34
Đầu ra:
3
Giải thích:
Đang tải editor...