Tích của ba số (Product of Three Numbers)

Hướng tiếp cận

Bài toán yêu cầu phân tích $n$ thành tích ba số nguyên phân biệt $a<b<c$ với $a,b,c\ge 2$. Vì $a<b<c$ và $a·b·c=n$ nên $a^3<n$, tức $a\le \sqrt[3]{n}$. Sau khi cố định $a$, ta cần phân tích $m=n/a$ thành tích hai số phân biệt $b<c$ với $b>a$, và ta có $b^2<m$ nên $b\le \sqrt{m}$.

Nhận xét quan trọng

1. Số ước nhỏ hơn hoặc bằng $\sqrt[3]{n}$ của $n$ rất ít (với $n\le {10}^9$ thì $\sqrt[3]{n}\le 1000$).
2. Sau khi tìm được $a$, ta cần $b>a$ và $c=m/b>b$, tương đương $b^2<m$.
3. Nếu không tìm được bộ nào, in NO.

Thuật toán

Với mỗi truy vấn $n$:

1. Duyệt $a$ từ $2$ đến $\sqrt[3]{n}$.
2. Nếu $a\mid n$, đặt $m=n/a$. Duyệt $b$ từ $a+1$ đến $\sqrt{m}$.
3. Nếu $b\mid m$, đặt $c=m/b$. Nếu $c>b$, ta đã tìm được bộ $(a,b,c)$, in YES và kết quả.
4. Nếu duyệt hết mà không tìm được, in NO.

Độ phức tạp

• Thời gian: $O(t·\sqrt[3]{n}·\sqrt{n/a})$ trong trường hợp xấu nhất, nhưng thực tế nhỏ hơn nhiều vì ta dừng ngay khi tìm được. Với $n\le {10}^9$ và $t\le 100$, thuật toán chạy rất nhanh.
• Bộ nhớ: $O(1)$.