Tác giả: Nguyễn Hữu Nhật Quang

Gọi ~f(i, j)~ là số cách để chọn các số từ ~a_1~ đến ~a_i~ tạo ra tích là ~j~ với ~j \le \sqrt{x}~.

Gọi ~g(i, k)~ là tổng số cách để chọn các số từ ~a_1~ đến ~a_i~ tạo ra tích là ~j~ với ~j > \sqrt{x}~ mà ~\lfloor \frac {x}{j} \rfloor = k~.

Ban đầu, ~f(0, 1) = 0~. Xét phần tử ~a_i~. Thao tác chuyển nhãn được thực hiện như sau:

• Với mỗi ~j \times a_i \le \sqrt{x}~: ~f(i, j \times a_i)~ được cộng thêm ~f(i - 1, j)~.
• Với mỗi ~j \le \sqrt{x}~ và ~j \times a_i > \sqrt{x}~: ~g(i, \lfloor \frac {x}{j \times a_i} \rfloor)~ được cộng thêm ~f(i - 1, j)~.
• Với mỗi ~k < \sqrt{x}~ và ~k \ge a_i~: ~g(i, \lfloor \frac {k}{a_i} \rfloor)~ được cộng thêm ~g(i - 1, k)~.

Độ phức tạp: ~O (n \times \sqrt{x})~.