灵魂碎片的收集

原题链接

TAG：数学，构造，哥德巴赫猜想

思路

当 \(x\) 为偶数时：

• 若 \(x-1\) 是质数，令 \(n\) 等于 \((x-1)^2\)，则 \(S(n)=1+(x-1)=x\)，满足条件；
• 若 \(x-3\) 是质数，令 \(n\) 等于 \((x-3)\times2\)，则 \(S(n)=1+2+(x-3)=x\)，满足条件。

当 \(x\) 为奇数时：

• 基于哥德巴赫猜想，我们可知，任意一个大于 \(2\) 的偶数可以拆成两个质数，假设两个质数为 \(p\) 和 \(q\)，那么 \(x-1=p+q\)，即 \(x=1+p+q\)，因此 \(S(n)=S(p\times q)=1+p+q\)。我们可以预处理出所有的质数，在 \([1,10^6]\) 范围内。枚举满足条件的质数即可得出答案。注意：当 \(x\le 7\) 的时候需要特判。

代码

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

const int N = 1E6 + 10;

int minp[N];
std::vector<int> primes;

void init() {
    for (int i = 2; i < N; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }

        for (auto p : primes) {
            if (i * p >= N) break;
            minp[i * p] = p;
            if (minp[i] == p) break;
        }
    }
}

void solve() {
    int x;
    cin >> x;
    if (x % 2 == 0) {
        if (minp[x - 1] == x - 1) cout << 1ll * (x - 1) * (x - 1) << "\n";
        else cout << 1ll * (x - 3) * 2 << "\n";
    } else {
        if (x == 1) cout << "2\n";
        else if (x == 3) cout << "4\n";
        else if (x == 5) cout << "-1\n";
        else if (x == 7) cout << "8\n";
        else {
            for (auto p : primes) {
                if (minp[x - 1 - p] == x - 1 - p) {
                    cout << 1ll * p * (x - 1 - p) << "\n";
                    return;
                }
            }
            cout << "-1\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}