~\color{orange}{\text{Hướng dẫn}}~

• Với ~d_1~ là số nguyên tố bất kì và ~f(a, b, c)~ là bộ ba số nguyên tố.

• Ta chứng minh 2 trường hợp: ~f(d_1, d_2, d_3) = f(d_1, d_1, 2 * d_1 - 1)~ hoặc/và ~f(d_1, d_2, d_3) = f(d_1, d_1, 2 * d_1 + 1)~

Có ~(d_1 + d_2)^2 - 1\ \vdots\ d_3 \Rightarrow d_1 + d_2 - 1\ \vdots\ d_3~ hoặc/và ~d_1 + d_2 + 1\ \vdots\ d_3~

TH1: ~d_1 + d_2 - 1\ \vdots\ d_3~

• Từ ~(d_1 + d_2 - 1\ \vdots\ d_3)~ và ~(d_1 + d_2 < 2 \times d_3)~ ~\Rightarrow~ ~d_3 = d_1 + d_2 - 1~

• Từ đó ~\Rightarrow ((2 \times d_1 - 1)^2\ \vdots\ d_2) \Rightarrow (4 \times d_1(d_1 - 1)\ \vdots\ d_2)~ mà ta có ~(d_1 \leq d_2)~ ~\Rightarrow (d_2 = d_1)~

• Vậy bộ ba số có dạng ~f(d_1, d_2, d_3) = f(d_1, d_1, 2 \times d_1 - 1)~

TH2: ~d_1 + d_2 + 1\ \vdots\ d_3~

• Chứng minh tương tự ta cũng có ~f(d_1, d_2, d_3) = f(d_1, d_1, 2 \times d_1 + 1)~

~\color{goldenrod}{\text{Tiếp cận}}~

• Bước đầu ta sàng nguyên tố, và đánh dấu các số là số nguyên tố

• Sau đó với mỗi số nguyên tố ~p~ từ nhỏ tới lớn dần.

Nếu ~2 \times p - 1~ là số nguyên tố, tăng biến đếm

• Trong lúc tăng biến đếm, nếu số lượng đó đúng bằng ~k~ thì ta xuất kết quả ~(p, p, 2p - 1)~

Nếu ~2 \times p + 1~ là số nguyên tố, tăng biến đếm

• Trong lúc tăng biến đếm, nếu số lượng đó đúng bằng ~k~ thì ta xuất kết quả ~(p, p, 2p + 1)~

• Lưu ý rằng với ~k = 60000~ thì mình cần sang tới ~9737954 \approx 10^7~

~\color{purple}{\text{Độ phức tạp}}~

• Ta có thể sàng nguyên tố và đánh dấu trong thời gian tuyến tính ~O(n)~

• Gọi ~\pi(n)~ là số số nguyên tố không lớn hơn ~n~. Ta cũng duyệt trong ~O(2 \times \pi(n))~

• Với giá trị ~k = X~ bất kì, có vẻ như đáp án tiến tới ~\approx 30,0312 \times X^{1,1518}~

Kết quả tính toán

Hàm tính phương trình xấp xỉ

• Vậy độ phức tạp của code dưới đây là ~O(30 \times n^{1,1518})~ cả thời gian và bộ nhớ

~\color{green}{\text{Code tham khảo }}~: Sàng nguyên tố, toán học

~^{^{\color{purple}{\text{Độ phức tạp : }} O(30 \times n^{1,1518})\ \color{purple}{\text{thời gian}}\ ||\ O(30 \times n^{1,1518})\ \color{purple}{\text{bộ nhớ}}}}~

#include <iostream>
#include <vector>

using namespace std;

/// Sàng nguyên tố tuyến tính - O(n)
vector<int> prime;
vector<int> lpf;
void sieve(int n)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

/// Kiểm tra nguyên tố - O(1)
bool isPrime(int x)
{
    return (x > 1) && (lpf[x] == x);
}

/// Giải bài toán - O(n^(1,1518))
int query(int n)
{
    for (int p : prime)
    {
        if (isPrime(p * 2 - 1))
        {
            if (--n == 0)
            {
                cout << p << ' ' << p << ' ' << p * 2 - 1;
                return 0;
            }
        }

        if (isPrime(p * 2 + 1))
        {
            if (--n == 0)
            {
                cout << p << ' ' << p << ' ' << p * 2 + 1;
                return 0;
            }
        }
    }
}

int main()
{
    sieve(1e7);
    int n;
    cin >> n;
    query(n);    
    return 0;
}