Nhận xét:

Với mọi số nguyên tố ~p~, gọi ~p_x~, ~p_y~, ~p_z~ lần lượt là số mũ của cơ số ~p~ trong phân tích thừa số nguyên tố của ~X~, ~Y~ và ~Z~, ta có ~p_y \leq p_z \leq p_x~. Bên cạnh đó, tổng các ~p_z~ (với mọi số nguyên tố ~p~) không vượt quá ~k~.

Lưu ý: các giá trị ~p~ không xuất hiện trong phân tích thừa số nguyên tố của ~X~ thì xem như ~p_x = 0~, tương tự với ~p_y~ và ~p_z~.

Với mỗi số nguyên tố ~p~, xem ~p_y, p_x~ như một cặp số ~(l, r)~, bài toán chuyển về như sau:

Có ~n~ cặp số ~(l, r)~, với mỗi cặp ~(l_i, r_i)~ cần chọn một số nguyên trong đoạn ~[l_i;r_i]~ sao cho tống các số được chọn không vượt quá ~k~.

Lưu ý, ta chỉ quan tâm đến những cặp ~(p_y, p_x)~ mà ~p~ xuất hiện trong phân tích thừa số của ~X~ hoặc ~Y~, vì khi ~p~ không xuất hiện trong cả hai thì ~p_x = p_y = 0~, vậy ~p_z = 0~ và không ảnh hưởng đến tổng các số được chọn.

Trong trường hợp số tồn tại ~p_y > p_x~, đáp án chắc chắn bằng ~0~.

Trở lại với bài toán, ta sử dụng quy hoạch động để giải quyết, cụ thể như sau. Gọi ~dp[i][j]~ là số cách chọn ~i~ số cho ~i~ cặp ~(l, r)~ đầu tiên mà tổng ~i~ số đó bằng ~j~.

Ta có ~dp[i][j] = \sum_{k = max(0, j - r_i)}^{j - l_i} dp[i - 1][j]~ ~\forall j \geq l_i~.

Để tính nhanh được tổng trên có thể dùng tổng tiền tố.

Độ phức tạp của thuật toán là ~O(n \times q)~.