谢谢

#include #include #include #include #include #include

using namespace std;

// 存储符合条件的5位素数（数字和、素数数值） vector<pair<int, int>> prime5; // 存储最终的解（25位数字组成的字符串，方便排序） vector solutions; // 当前填充的方阵 int grid[5][5]; // 目标数字和、左上角固定数字 int target_sum, top_left;

// 素数筛选：判断一个数是否为素数 bool is_prime(int num) { if (num < 2) return false; if (num == 2) return true; if (num % 2 == 0) return false; for (int i = 3; i <= sqrt(num); i += 2) { if (num % i == 0) return false; } return true; }

// 预处理所有5位素数，并计算其各位数字和 void preprocess_primes() { prime5.clear(); // 5位素数范围：10000 ~ 99999 for (int num = 10000; num <= 99999; num++) { if (is_prime(num)) { // 计算各位数字和 int sum = 0; int tmp = num; while (tmp > 0) { sum += tmp % 10; tmp /= 10; } prime5.emplace_back(sum, num); } } }

// 检查一个5位数是否是符合条件的素数（数字和为target_sum） bool is_valid_prime(int num) { if (num < 10000 || num > 99999) return false; int sum = 0; int tmp = num; while (tmp > 0) { sum += tmp % 10; tmp /= 10; } return sum == target_sum && is_prime(num); }

// 将一行转换为5位数 int row_to_num(int row) { int num = 0; for (int col = 0; col < 5; col++) { num = num * 10 + grid[row][col]; } return num; }

// 将一列转换为5位数 int col_to_num(int col) { int num = 0; for (int row = 0; row < 5; row++) { num = num * 10 + grid[row][col]; } return num; }

// 主对角线（左上到右下）转换为5位数 int diag1_to_num() { int num = 0; for (int i = 0; i < 5; i++) { num = num * 10 + grid[i][i]; } return num; }

// 副对角线（右上到左下）转换为5位数 int diag2_to_num() { int num = 0; for (int i = 0; i < 5; i++) { num = num * 10 + grid[i][4 - i]; } return num; }

// 将方阵转换为25位字符串（用于排序） string grid_to_string() { string s; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { s += to_string(grid[i][j]); } } return s; }

// 验证整个方阵是否符合所有条件 bool validate_grid() { // 检查所有行 for (int i = 0; i < 5; i++) { int num = row_to_num(i); if (!is_valid_prime(num)) return false; } // 检查所有列 for (int j = 0; j < 5; j++) { int num = col_to_num(j); if (!is_valid_prime(num)) return false; } // 检查两条对角线 if (!is_valid_prime(diag1_to_num())) return false; if (!is_valid_prime(diag2_to_num())) return false; return true; }

// 回溯填充方阵（row:当前行, col:当前列） void backtrack(int row, int col) { // 终止条件：所有位置填充完成 if (row == 5) { if (validate_grid()) { solutions.push_back(grid_to_string()); } return; }

// 计算下一个位置
int next_row = row, next_col = col + 1;
if (next_col == 5) {
    next_row = row + 1;
    next_col = 0;
}

// 左上角固定，直接填充并递归
if (row == 0 && col == 0) {
    grid[row][col] = top_left;
    backtrack(next_row, next_col);
    return;
}

// 填充当前位置：0-9（但首位不能为0）
for (int digit = 0; digit <= 9; digit++) {
    // 行首/列首不能为0
    if ((col == 0 && digit == 0) || (row == 0 && digit == 0)) {
        continue;
    }

    grid[row][col] = digit;

    // 剪枝：如果当前行已填充完成，先检查该行是否为有效素数
    if (col == 4) {
        int row_num = row_to_num(row);
        if (!is_valid_prime(row_num)) {
            continue;
        }
    }
    // 剪枝：如果当前列已填充完成，先检查该列是否为有效素数
    if (row == 4) {
        int col_num = col_to_num(col);
        if (!is_valid_prime(col_num)) {
            continue;
        }
    }

    // 递归填充下一个位置
    backtrack(next_row, next_col);
}

}

// 输出单个解（按格式） void print_solution(const string& s) { for (int i = 0; i < 25; i += 5) { for (int j = 0; j < 5; j++) { if (j > 0) cout << " "; cout << s[i + j]; } cout << endl; } }

int main() { // 输入：数字和、左上角数字 cin >> target_sum >> top_left;

// 预处理5位素数
preprocess_primes();

// 初始化方阵
memset(grid, 0, sizeof(grid));

// 回溯求解
backtrack(0, 0);

// 排序解（按25位数字大小）
sort(solutions.begin(), solutions.end());

// 输出结果
if (solutions.empty()) {
    cout << "NONE" << endl;
} else {
    for (int i = 0; i < solutions.size(); i++) {
        print_solution(solutions[i]);
        // 两组解之间输出空行（最后一组不输出）
        if (i != solutions.size() - 1) {
            cout << endl;
        }
    }
}

return 0;

}

题目描述 在下面的方格中，每行，每列，以及两条对角线上的数字可以看作是五位的素数。方格中的行按照从左到右的顺序组成一个素数，而列按照从上到下的顺序。两条对角线也是按照从左到右的顺序来组成。

+---+---+---+---+---+ | 1 | 1 | 3 | 5 | 1 | +---+---+---+---+---+ | 3 | 3 | 2 | 0 | 3 | +---+---+---+---+---+ | 3 | 0 | 3 | 2 | 3 | +---+---+---+---+---+ | 1 | 4 | 0 | 3 | 3 | +---+---+---+---+---+ | 3 | 3 | 3 | 1 | 1 | +---+---+---+---+---+ 这些素数各个数位上的和必须相等。

左上角的数字是预先定好的。

一个素数可能在方阵中重复多次。

如果不只有一个解，将它们全部输出（按照这25个数字组成的25位数的大小排序）。

一个五位的素数开头不能为0（例如：00003 不是五位素数）

输入 一行包括两个被空格分开的整数:各个位的数字和 和左上角的数字。

输出 对于每一个找到的方案输出5行，每行5个字符, 每行可以转化为一个5位的质数.在两组方案中间输出一个空行. 如果没有解就单独输出一行"NONE"。

样例 输入数据 1 11 1 输出数据 1 11351 14033 30323 53201 13313

11351 33203 30323 14033 33311

13313 13043 32303 50231 13331 来源