Bổ đề: Nếu ~n > 1~ thì dãy số thỏa mãn không chứa số ~2~:

Gọi ~M~ là trung bình cộng của dãy số. Ta thấy ~M~ là số nguyên tố và do ~n > 1~ nên ~M > 2~ ~\Rightarrow~ ~M~ là số nguyên tố lẻ. Giả sử dãy số thỏa mãn chứa số ~2~:

--- Nếu ~n~ chẵn thì tổng của dãy số là ~M \times n~ là số chẵn. Mặt khác ta lại có tổng của dãy số là ~2 + (n - 1~ số nguyên tố lẻ~)~ là số lẻ. ~\Rightarrow~ Mâu thuẫn.

--- Nếu ~n~ lẻ thì tổng của dãy số là ~M \times n~ là số lẻ. Mặt khác ta lại có tổng của dãy số là ~2 + (n - 1~ số nguyên tố lẻ~)~ là số chẵn. ~\Rightarrow~ Mâu thuẫn.

Như vậy dãy số thỏa mãn không chứa số ~2~. Trong khi code, ta chỉ xét các số nguyên tố lớn hơn ~2~.

1. ~100 < n \leq 1000~:

Sinh ngẫu nhiên ra dãy số bất kì cho đến khi tìm được dãy số thỏa mãn.

2. ~1000 < n \leq 50000~:

Sinh ngẫu nhiên ra một số nguyên tố ~p~ gần ~\frac{10^7}{2} = 5 \cdot 10^6~ bất kì rồi tìm mọi cặp ~p - x~, ~p + x~ mà cả hai đều là số nguyên tố.

3. ~50000 < n \leq 400000~:

Dùng thuật toán backtrack để tìm dãy số thỏa mãn.

4. ~400000 < n~:

Có nhiều cách giải, ví dụ như:

--- Tối ưu thuật toán backtrack bằng cách shuffle dãy số nguyên tố.

--- Tối ưu thuật toán sinh ngẫu nhiên bằng cách mỗi lần thay đổi chỉ thay đổi một vị trí.

--- Thử tất cả các dãy số gồm các nguyên tố liên tiếp cho tới khi tìm được dãy số thỏa mãn.

5. Bonus: Giá trị n lớn nhất có thể đạt được là bao nhiêu?

Dãy số thỏa mãn dài nhất có độ dài là: ~664576~. (Số lượng số nguyên tố ~-~ ~3~)

Ta có thể đoán được giá trị này vì theo giả thuyết Goldbach yếu, luôn biểu diễn được một số dưới dạng tổng của ~3~ số nguyên tố và do các số nguyên tố khá ngẫu nhiên nên khả năng cao sẽ tìm được một số nguyên tố ~p~ sao cho tổng mọi số nguyên tố ~-~ ~p \times 664576~ có thể biểu diễn được bằng ba số nguyên tố khác nhau.

Ta sẽ tìm dãy số thỏa mãn có độ dài là ~664576~ bằng cách chọn tất cả các số nguyên tố lớn hơn ~2~ sau đó thử tất cả các cách bỏ ~2~ số nguyên tố đi cho tới khi tìm được dãy số thỏa mãn. Có thể tối ưu thuật toán này bằng FFT.

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

const int NM = 1e7;

vector<int> prime;
bool is_prime[NM];

void init() {
    for (int i = 2; i < NM; ++i)
        is_prime[i] = 1;

    for (int i = 2; i < NM; ++i)
        if (is_prime[i]) {
            if (i > 2)
                prime.push_back(i);

            if (i <= NM / i)
                for (int j = i * i; j < NM; j += i)
                    is_prime[j] = 0;
        }
}

int n;
vector<int> a;

void trau(int id, int cnt, long long s) {
    if (cnt == n) {
        if (s % n == 0 && is_prime[s / n]) {
            cout << n << "\n";
            for (auto &i: a) cout << i << " ";
            exit(0);
        }
        return;
    }

    if (id == prime.size()) return;

    a.emplace_back(prime[id]);
    trau(id + 1, cnt + 1, s + prime[id]);
    a.pop_back();
    trau(id + 1, cnt, s);
}

void solve() {
    n = 600000;
    shuffle(prime.begin(), prime.end(), mt19937(0));
    trau(0, 0, 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    solve();
}