Tutorial — Hệ tam phân

Phép toán `` `tor` `` thực hiện cộng từng cặp chữ số theo hệ tam phân và hoàn toàn không có phần nhớ giữa các hàng. Do đó, việc tìm $b$ tương đương với việc xác định từng chữ số tam phân của $b$ sao cho thỏa mãn điều kiện với từng cặp chữ số của $a$ và $c$.

Gọi $d_a$, $d_b$ và $d_c$ là các chữ số ở cùng một hàng trong hệ tam phân của $a$, $b$ và $c$, ta có quan hệ $(d_a + d_b) \equiv d_c \pmod 3$. Quan hệ này cho phép ta biểu diễn trực tiếp chữ số chưa biết $d_b$ qua hai chữ số đã cho.

Vì các hàng được xử lý hoàn toàn độc lập và không ảnh hưởng lẫn nhau, ta có thể giải quyết bài toán bằng cách tách lần lượt từng chữ số từ hàng thấp đến hàng cao. Việc này giúp tìm ra giá trị của $b$ một cách chính xác mà không cần duyệt qua tất cả các khả năng.

Sử dụng vòng lặp chia nguyên cho $3$ để lấy từng chữ số của $a$ và $c$, tính $d_b = (d_c - d_a + 3) \pmod 3$, rồi nhân với lũy thừa tương ứng của $3$ để cộng dồn vào kết quả cuối cùng. Thuật toán này có độ phức tạp thời gian $O(\log_3(\max(a, c)))$.