Tóm tắt đề bài

Cho hai số nguyên dương ~A~ và ~B~. Một tháp đầy đủ là một dãy các số ~x_1, x_2, ..., x_k~ sao cho:

• ~x_1 = A~, ~x_k = B~.
• ~x_i~ chia hết cho ~x_{i - 1}~.
• Không tồn tại ~z~ sao cho ~z~ chia hết cho ~x_{i - 1}~ và ~x_i~ chia hết cho ~z~.

Tìm độ dài của tháp đầy đủ đó, có thể chứng minh độ dài đó là duy nhất. Đồng thời trong tất cả các tháp đầy đủ, tìm tháp có ~x_1 + x_2 + ... + x_k~ nhỏ nhất.

Lời giải

• Nhận xét 1: Nếu ~B~ không chia hết cho ~A~, không tồn tại tháp đầy đủ. Ta in ra ~-1~.
• Nhận xét 2: Đặt ~z_i = \frac {x_i}{x_{i - 1}}~. Ta thấy ~z_2 \times z_3 \times ... \times z_k = \frac {B}{A}~.
• Nhận xét 3: ~z_i~ là số nguyên tố. Nếu ~z_i~ không là số nguyên tố, ta sẽ có thể chèn thêm phần tử vào dãy đầy đủ này.

Vậy ta sẽ phân tích ~\frac {B}{A}~ ra thừa số nguyên tố. Vấn đề chỉ là bố trí các thừa số này theo thứ tự nào.

Thứ tự tối ưu chắc chắn là thứ tự mà các thừa số nguyên tố tăng dần. Đây là điều dễ dàng quan sát thấy, vì ta mong muốn các số nhỏ sẽ được xuất hiện (hay có đóng góp) nhiều lần hơn các số lớn.

Độ phức tạp: ~O~ (~\sqrt \frac {B}{A}~).