Hướng dẫn giải

Bài yêu cầu phân tích $n$ thành thừa số nguyên tố, liệt kê các thừa số (kể cả lặp lại) theo thứ tự tăng dần, rồi in thừa số thứ $k$. Nếu số thừa số ít hơn $k$ thì in $-1$.

Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^6~

Thử mọi số $d$ từ $2$ đến $n$. Mỗi khi $d$ chia hết số còn lại $m$ thì ghi $d$ vào danh sách và chia $m$ cho $d$, lặp lại cho đến khi không chia hết nữa. Vì thử $d$ theo thứ tự tăng dần nên danh sách đã được sắp xếp sẵn.

Kết quả chấm riêng sub này: đúng 11/21 test (các test còn lại quá giờ vì $n$ lớn hơn miền của sub).

Sub 2: Thử đến căn bậc hai — ~O(\sqrt{n})~, dùng cho ~n \le 10^9~

Nếu $m$ có ước nguyên tố $d$ thì $d$ không vượt quá $\sqrt{m}$, trừ khi $m$ là một số nguyên tố lớn. Vì vậy chỉ cần thử $d$ với $d \cdot d \le m$ và chia hết đến hết. Sau vòng lặp, nếu $m > 1$ thì $m$ chính là một thừa số nguyên tố lớn nhất và được thêm vào cuối danh sách.

Bẫy cần chú ý: khi thử $d \cdot d \le m$ phải dùng kiểu long long để tránh tràn số, và $m$ thay đổi trong lúc chia nên điều kiện dừng dùng $m$ hiện tại.

Kết quả chấm riêng sub này: đúng 21/21 test.

Chương trình hoàn chỉnh

Chương trình đọc $T$, rồi với mỗi test đọc $n, k$. Nếu $n \le 10^6$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.

#include <bits/stdc++.h>
using namespace std;

long long n;
int k;

// Sub 1: vét cạn — thử mọi ước d từ 2 đến n, chia hết thì lấy hết thừa số d
// Dùng khi n <= 10^6
void sub1() {
    vector<long long> f;
    long long m = n;
    for (long long d = 2; d <= m; d++)
        while (m % d == 0) { f.push_back(d); m /= d; }
    if (k > (int)f.size()) cout << -1 << "\n";
    else cout << f[k - 1] << "\n";
}

// Sub 2: thử chia đến căn bậc hai của n — dùng cho n lớn (đến 10^9)
// Sau khi chia hết hết các ước <= sqrt(m), phần m còn lại (nếu > 1) là một thừa số nguyên tố lớn
void sub2() {
    vector<long long> f;
    long long m = n;
    for (long long d = 2; d * d <= m; d++)
        while (m % d == 0) { f.push_back(d); m /= d; }
    if (m > 1) f.push_back(m);
    if (k > (int)f.size()) cout << -1 << "\n";
    else cout << f[k - 1] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        if (n <= 1000000) sub1();   // n nhỏ: vét cạn cho chắc
        else sub2();                // n lớn: chỉ thử đến căn bậc hai
    }
    return 0;
}