Subtask 1 ($n \leq 100, k \leq 3$)

Subtask này để mọi người duyệt trâu với độ phức tạp $O(T \times n^2)$, không có gì đáng nói.

Subtask 2 ($n \leq 5000$)

Sử dụng thuật toán $O(\sqrt{n})$ để tăng tốc độ đếm ước của một số nguyên

Độ phức tạp được giảm xuống $O(T \times n \sqrt{n})$

Subtask 3 ($n \leq 3 \times 10^5$)

Sử dụng sàng Eratosthenes để tìm nhanh số ước của tất cả các số bé hơn $3 \times 10^5$ trong $O(n \text{ log } n)$, sau đó với mỗi test, ta có thể tìm số số $k$ ước trong $O(n)$

Độ phức tạp: $O(n \text{ log } n + T \times n)$

Subtask 4 ($n \leq 10^7; k \leq 5$)

Sử dụng công thức tính ước của một số sau khi phân tích thành thừa số nguyên tố.

Cụ thể, nếu ta phân tích $x$ thành thừa số nguyên tố: $x = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_n^{a_n}$ với $p_1, p_2, \ldots, p_n$ là các số nguyên tố phân biệt và $a_1, a_2, \ldots a_n$ là các số nguyên dương thì số ước của $x$ là $(a_1 +1) \times (a_2 + 1) \times \ldots \times (a_n+1)$

Mà với $k \leq 5$, dễ thấy mọi số $x$ thỏa mãn đều không có $n > 2$ ($n$ là số ước nguyên tố phân biệt của $x$). Có thể dễ dàng chứng minh điều này bằng phản chứng. Do đó, ta chỉ cần xét hai trường hợp:

n = 1

Khi đó các số $x$ thỏa mãn sẽ có dạng $x = p^{k-1}$ với $p$ là một số nguyên tố. Ta chỉ cần đếm số số nguyên tố $p$ thỏa mãn $p^{k-1} \leq n$.

n = 2

Khi đó, $x = p_1^{d_1-1} \times p_2^{d_2-1}$ với $d_1 \times d_2 = k$ và $d_1,d_2 > 1$. Ta có thể dễ dàng duyệt qua mọi cặp $(d_1,d_2)$.

Ứng với mỗi cặp, ta sẽ giả sử $p_1 < p_2$, từ đó suy ra $p_1 < \sqrt[(d_1+d_2)]{n}$. Ta có thể duyệt qua từng giá trị $p_1$ và đếm số số nguyên tố $p_2$ thỏa mãn $p_1 < p_2 \leq \sqrt[d_2]{\frac{n}{p_1}}$

Việc đếm số nguyên tố ta có thể dùng sàng Eratosthenes, nhưng lần này trong $O(n \text{ log log } n)$, cộng thêm $O(n)$ cho mảng cộng dồn phục vụ đếm số nguyên tố trong khoảng.

Subtask 5 ($n \leq 10^9; k \leq 10$)

Lúc này ta không thể đếm số nguyên tố bằng sàng Eratosthenes nữa, mà ta sẽ dùng thuật toán Meissel-Lehmer để đếm trong $O(n^{\frac{2}{3}})$

Thuật toán subtask này cũng gần như tương tự subtask 4, trừ việc phải xét thêm một trường hợp khi $k = 8$. Lúc này $8$ có thể phân tích thành $2 \times 2 \times 2$, do đó $n \leq 3$. $8$ cũng là số duy nhất trong khoảng $[1,10]$ có thể có $n = 3$.

$k = 8, n = 3$

Lúc này ta cần tìm 3 số nguyên tố phân biệt $p_1, p_2, p_3$ sao cho $p_1 \times p_2 \times p_3 \leq n$

KMTTQ, giả sử $p_1 < p_2 < p_3$. Dễ thấy $p_1 < \sqrt[3]{n}$ và $p_2 \leq \sqrt{\dfrac{n}{p_1}}$. Do đó, ta có thể duyệt qua tất cả các cặp $(p_1, p_2)$ rồi đếm số số nguyên tố $p_3$ thỏa mãn $p_2 < p_3 \leq \dfrac{n}{p_1p_2}$