Ước số thứ k

Lời giải: Ước số thứ k

Hướng tiếp cận

Liệt kê các ước số nhỏ hơn hoặc bằng $\sqrt{n}$, sau đó suy ra các ước lớn.

Nhận xét quan trọng

1. Nếu $d$ là ước của $n$ và $d\le \sqrt{n}$, thì $n/d$ cũng là ước và $n/d\ge \sqrt{n}$.

2. Số ước nhỏ $\le \sqrt{n}$ tối đa là $\sqrt{n}\approx {10}^{7.5}$ với $n={10}^{15}$.

3. Các ước của $n$ có thể chia thành:

   • Ước nhỏ: $d$ với $d\le \sqrt{n}$
   • Ước lớn: $n/d$ với $d\le \sqrt{n}$ và $d\ne n/d$

Thuật toán

1. Duyệt $d$ từ $1$ đến $\sqrt{n}$, lưu các ước nhỏ vào mảng.
2. Tính tổng số ước: $2m-1$ nếu $n$ là số chính phương, $2m$ nếu không (với $m$ = số ước nhỏ).
3. Nếu $k>$ tổng số ước: in $-1$.
4. Nếu $k\le m$: in ước nhỏ thứ $k$.
5. Ngược lại: in $n/$ ước nhỏ thứ $(total-k+1)$.

Độ phức tạp

• Thời gian: $O(\sqrt{n})$
• Bộ nhớ: $O(\sqrt{n})$ (tối đa $~{10}^7$ ước nhỏ)