結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
 
// 判断素数的函数（这里数值较小，用简单方法即可）
bool isPrime(int x) {
    if(x < 2) return false;
    for (int i = 2; i * i <= x; i++){
        if(x % i == 0)
            return false;
    }
    return true;
}
 
// 主函数
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int K;
    cin >> K;
    
    // 注意：题目要求 0 <= K <= 10000
    // 构造思路：
    // 将数列分为两个模块：
    //  模块 P：用数字 1；它们之间任一数对之和为 1+1 = 2 (素数)。
    //  模块 Q：将另外一部分再分为两组，
    //         分别赋值为 3 和 8。因为 3+8 = 11 是素数，
    //         而 3+3 = 6、8+8 = 16 均为合数。
    // 同时保证模块 P 与模块 Q 的混合配对均为合数：
    //    1+3 = 4,  1+8 = 9.
    //
    // 因此如果模块 P 中有 x 个 1，
    //  它们贡献的素数对为 C(x,2) = x*(x-1)/2;
    // 如果模块 Q 中左侧（数字3）的个数为 a，
    //  右侧（数字8）的个数为 b，则贡献素数对为 a*b.
    //
    // 总数对数为:  x*(x-1)/2 + a*b = K.
    // 同时序列总长度: N = x + a + b (要求 N <= 250).
    //
    // 接下来遍历 x, a, b 寻找满足条件的一个解：
    
    // 特殊处理 K == 0：至少输出一个数（例如 1）即可，因为没有任何两数之和要为素数。
    if(K == 0){
        cout << 1 << "\n" << 1 << "\n";
        return 0;
    }
    
    bool found = false;
    int X = -1, A = -1, B = -1;
    // x取值范围 0 <= x <= 250
    for (int x = 0; x <= 250 && !found; x++){
        // 模块 P 内贡献： x*(x-1)/2
        int base = x * (x - 1) / 2;
        // 若 base > K，则后面x更大时肯定超出 K
        if(base > K) break;
        
        // 接下来求 a, b 非负整数使得:
        //      base + a*b = K  <==>  a*b = (K - base)
        int rem = K - base;
        
        // 枚举 a，从 0 到 (250 - x)（因为后面 a+b 要加上 x 不超过 250）
        for (int a = 0; a <= 250 - x && !found; a++){
            // 如果 a 为0，则 a*b 为0，因此只有当 rem==0时可行，此时 b 必须为 0；
            // 但注意 K>0时 rem > 0，所以 a==0只能用于 K==base (即 K为三角形数)。
            if(a == 0){
                if(rem == 0){
                    // 令 b = 0
                    int b = 0;
                    if(x + a + b <= 250 && x + a + b >= 1){
                        X = x; A = a; B = b;
                        found = true;
                    }
                }
                continue;
            }
            // 当 a > 0 时，要求 rem 必须能被 a 整除
            if(rem % a != 0) continue;
            int b = rem / a;
            // 同时要求 a+b 不超过 (250 - x)
            if(a + b <= 250 - x){
                X = x; A = a; B = b;
                found = true;
                break;
            }
        }
    }
    
    if(!found){
        //按照题目范围，通常总能构造出解（下面这种构造满足题意）。
        cout << -1 << "\n";
        return 0;
    }
    
    int N = X + A + B;
    cout << N << "\n";
    // 根据构造方案，序列分为两块：
    // 模块 P：输出 X 个 1；
    // 模块 Q：输出 A 个 3 和 B 个 8.
    // 数值范围内均满足 1 <= c_i <= 1000000.
    
    // 输出模块 P
    for (int i = 0; i < X; i++){
        cout << 1 << " ";
    }
    // 输出模块 Q：先 A 个 3
    for (int i = 0; i < A; i++){
        cout << 3 << " ";
    }
    // 再 B 个 8
    for (int i = 0; i < B; i++){
        cout << 8 << " ";
    }
    cout << "\n";
    
    return 0;
}
0