[HSG_ST_24] Nhà toán học tài ba

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.3s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Pascal, Python

Trong một ngôi làng nhỏ có tên là Prime Ville, người dân nơi đây có truyền thống tôn vinh những con số nguyên tố. Hằng năm, vào ngày lễ hội lớn nhất làng, dân làng sẽ tổ chức một cuộc thi để tìm ra những con số nguyên tố đặc biệt. Người chiến thắng sẽ được nhận danh hiệu "Nhà Toán Học Tài Ba". Năm nay, bài toán mà trường làng đưa ra như sau: "Hãy tìm ra số nguyên tố nhỏ thứ ~K~ trong danh sách số nguyên tố tìm được từ ~N~ số nguyên mà ta đã chuẩn bị".

Yêu cầu

Em hãy viết chương trình để giúp dân làng tìm ra kết quả câu đố nhanh nhất.

Dữ liệu đầu vào

Gồm hai dòng:

Dòng đầu tiên ghi hai số nguyên ~N~ và ~K~ ~(1 \le N \le 10^5;\ 1 \le K < N)~.
Dòng tiếp theo ghi ~N~ số nguyên ~A_i~ ~(0 < A_i \le 10^9)~.

Chú ý: Do đề không nói rõ, trong bộ test tôi đã giả định rằng các số đều khác nhau đôi một. Tôi cũng đã điều chỉnh bộ test phù hợp để có thể AC câu này trong thời gian xấp xỉ 1 giây. Tuy nhiên, nếu trong trường hợp tệ hơn, đặc biệt là khi ~K~ lớn và số nguyên tố xuất hiện dày đặc, việc sử dụng thuật toán có độ phức tạp là ~\mathcal{O}(N\sqrt{X})~ là chưa đủ tốt để đảm bảo thời gian chạy xấp xỉ 1 giây (nếu không dùng thuật toán Rabin-Miller)

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số nguyên tố nhỏ thứ ~K~ tìm được, nếu không tìm được, in ra ~-1~.

Ràng buộc dữ liệu

Có 50% số điểm tương ứng với 50% số test thỏa ~1 \le N \le 20;\ 0 < A_i \le 10^4~.
Có 50% số điểm tương ứng với 50% số test thỏa ~N \le 10^5;\ 0 < A_i \le 10^9~.

Ví dụ

Ví dụ 1

INPUT

10 3
2 8 5 3 7 10 11 4 6 13

OUTPUT

Bình luận

Hãy đọc nội quy trước khi bình luận.

hoanglan_nd_502 đã bình luận lúc 15, Tháng 6, 2025, 8:27 ← sửa 4 →

pragma GCC optimize("03,unroll-loops")

pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

bool nt(int n){
    if (n==2||n==3||n==5) return true;
    if (n%2==0||n%3==0) return false;
    for (int i=5;i<=sqrt(n);i+=6){
        if (n%i==0||n%(i+2)==0) return false;
    }
    return true;
}

ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
v<int> a(n),ve;
for (int i=0;i&lt;n;i++){cin>>a[i];if (nt(a[i])) ve.pb(a[i]);}
if (ve.size()==0||ve.size()&lt;k){
    cout<<-1;
    return 0;
}
sort(ve.begin(),ve.end());
cout<&lt;ve[k-1];

cách này không bị tle mà ac full nhé , có mấy chỗ lỗi kí tự thì tự xử nhé:vv