Subtask ~1~: Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thoả mãn: ~N, Q \le 1000~; ~A_i \le 1000~ với mọi ~1 \le i \le N~; ~P_i \le 1000~ với mọi ~1 \le i \le Q~.

Gọi ~MaxA = max_i A[i]~, với mọi ~1 \le i \le N~. Với mỗi giá trị ~x~, theo thứ tự từ ~1~ đến ~MaxA~, xét lần lượt từng phần tử của mảng ~A~ và tạo ra mảng ~D~ bằng cách bổ sung ~x~ vào cuối mảng ~D~. Việc trả lời từng câu hỏi trong ~Q~ câu hỏi thuộc mảng ~P~ được thực hiện trong ~O(1)~.

Độ phức tạp: ~O(MaxA \times N)~.

Subtask ~2~: ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~A_i~ là số nguyên tố với mọi ~1 \le i \le N~.

Vì các giá trị trong mảng ~A~ là số nguyên tố nên mảng ~D~ chứa ~N~ giá trị bằng ~1~ và ~N~ giá trị phần tử của mảng ~A~ theo thứ tự tăng dần. Từ đó dễ dàng trả lời trong ~O(1)~ với mỗi câu hỏi trong ~Q~ câu hỏi.

Độ phức tạp: ~O(MaxA + N + Q)~.

Subtask ~3~: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 10 000~; ~P_i \le 2 \times 10^6~ với mọi ~1 \le i \le Q~.

Đối với mỗi phần tử trong mảng ~A~, xác định các ước số của nó trong ~O(\sqrt{MaxA})~. Lưu các phần tử thuộc mảng ~D~ bằng cách lưu trữ dưới dạng vectơ tần số chỉ số lượng xuất hiện mỗi ước số phân biệt trong mảng ~D~. Dựa vào đó, xây dựng mảng ~D~ và trả lời mỗi câu hỏi trong ~O(1)~.

Độ phức tạp: ~O(N \times \sqrt{MaxA + MaxP}), với ~MaxP = max_i P[i]~, với mọi ~1 \le i \le Q~.

Subtask ~4~: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~P_i \le 2 \times 10^6~ với mọi ~1 \le i \le Q~.

Ta xây dựng một vectơ ~NMul~ lưu trữ, với mỗi giá trị ~x~ từ ~1~ đến ~MaxA~, có bao nhiêu số trong mảng ~A~ được chia bởi ~x~ sẽ được giữ lại. Việc xây dựng được thực hiện trong ~O(MaxA \times log(MaxA)~, tương tự như phương pháp sàng Eratosthenes. Dựa trên vectơ này, xây dựng mảng ~D~ và trả lời mỗi câu hỏi trong ~O(1)~.

Độ phức tạp: ~O(MaxA \times log(MaxA) + Q)~.

Subtask ~5~: ~10\%~ test còn lại ứng với ~10\%~ số điểm của bài: Không có ràng buộc gì thêm.

Ta xây dựng vectơ ~NMul~ như trong Subtask ~4~. Ta xây dựng mảng ~D~ bằng cách lưu dưới dạng (ước số, tần số xuất hiện). Sử dụng tổng cộng dồn các tần số để lưu vị trí cuối cùng của mỗi ước số ~x~ xuất hiện trong danh sách các ước số. Vì mảng các vị trí này ngày càng tăng nên để trả lời mỗi câu hỏi trong ~Q~ câu hỏi, ta có thể sử dụng tìm kiếm nhị phân.

Độ phức tạp: ~O(MaxA \times log(MaxA) + Q \times log(MaxA))~.