結果

問題 No.689 E869120 and Constructing Array 3
コンテスト
ユーザー 梧桐
提出日時 2025-11-18 03:42:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 4,107 bytes
コンパイル時間 1,575 ms
コンパイル使用メモリ 169,528 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-18 03:42:37
合計ジャッジ時間 3,257 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int K;
    cin >> K;
    if (K == 0) {
        // 情况 K=0：只取一个数即可
        cout << 1 << "\n" << 1 << "\n";
        return 0;
    }

    // 生成素数表（到一定上界，例如50000），用于后续构造
    int MAXN = 50000;
    vector<bool> isPrime(MAXN+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAXN; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 收集素数列表
    vector<int> primes;
    for (int i = 2; i <= MAXN; i++) {
        if (isPrime[i]) primes.push_back(i);
    }

    // 针对 K <= 249 的情况：一条 1 加上 K 个 (p_i - 1)
    if (K <= 249) {
        int N = K + 1;
        cout << N << "\n";
        cout << 1;
        int used = 0;
        // 素数序列从3开始（跳过2）作为 p_i
        for (int i = 0; i < (int)primes.size() && used < K; i++) {
            if (primes[i] == 2) continue;
            cout << " " << primes[i] - 1;
            used++;
        }
        cout << "\n";
        return 0;
    }

    // 情况 K >= 250 或未被上述覆盖，尝试因子分解法：使用奇数 3 的群组
    bool done = false;
    for (int A = 2; A <= 250; A++) {
        if (K % A != 0) continue;
        int X = K / A;
        if (A + X > 250) continue;
        // 找到方案：使用 A 个 '3' 和 X 个 (素数 - 3)
        cout << (A + X) << "\n";
        // A 个 3
        for (int i = 0; i < A; i++) {
            cout << 3 << (i+1 < A ? " " : (X>0 ? " " : "\n"));
        }
        // X 个素数-3（跳过前两个素数2,3）
        int used = 0;
        for (int i = 0; i < (int)primes.size() && used < X; i++) {
            if (primes[i] <= 3) continue;
            cout << (primes[i] - 3);
            used++;
            if (used < X) cout << " ";
        }
        cout << "\n";
        done = true;
        break;
    }
    if (done) return 0;

    // 双群组情况：奇数部分用一个 '1' 和 B 个 '3'
    // 枚举 B (3 的个数) 和 y (#Y列表偶数)，求解 x = K - B*y
    // 要求 1 + B + x + y <= 250
    // 首先构造 X_list 和 Y_list：满足 1+E 素数且 3+E 非素数，以及 3+E 素数且 1+E 非素数
    vector<int> X_list, Y_list;
    for (int e = 2; e <= MAXN && ((int)X_list.size() < 300 || (int)Y_list.size() < 300); e++) {
        if (e % 2 != 0) continue; // 只考虑偶数
        bool p1 = (e+1 <= MAXN ? isPrime[e+1] : false);
        bool p2 = (e+3 <= MAXN ? isPrime[e+3] : false);
        if (p1 && !p2 && (int)X_list.size() < 300) {
            X_list.push_back(e);
        }
        if (p2 && !p1 && (int)Y_list.size() < 300) {
            Y_list.push_back(e);
        }
    }
    int foundB=-1, foundX=-1, foundY=-1;
    for (int B = 2; B <= 250; B++) {
        // 条件必须：1 + B + x + y <= 250 -> x + y <= 249 - B
        // 遍历 y
        for (int y = 0; y <= 249 - B; y++) {
            int x = K - B*y;
            if (x < 0) break;
            if (x + y <= 249 - B) {
                // 找到解
                foundB = B; foundX = x; foundY = y;
                break;
            }
        }
        if (foundB != -1) break;
    }
    if (foundB == -1) {
        // 理论上不可能到达这里，但保底处理
        // 回退成所有 1 的方案（K<=249 时处理）或异常
        cout << 1 << "\n" << "1\n";
        return 0;
    }
    // 输出 1 + B 次 3 + x 次 X_list + y 次 Y_list
    int B = foundB, x = foundX, y = foundY;
    int N = 1 + B + x + y;
    cout << N << "\n";
    cout << 1;
    // B 个 3
    for (int i = 0; i < B; i++) {
        cout << " " << 3;
    }
    // x 个来自 X_list 的偶数
    for (int i = 0; i < x && i < (int)X_list.size(); i++) {
        cout << " " << X_list[i];
    }
    // y 个来自 Y_list 的偶数
    for (int i = 0; i < y && i < (int)Y_list.size(); i++) {
        cout << " " << Y_list[i];
    }
    cout << "\n";
    return 0;
}
0