\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\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;
}