质数方阵

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2821 字
预处理素数前缀，逐行 DFS 剪枝构造方阵
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1446
// 题意：给数字和 S 与左上角数字，构造 5 * 5 方阵，使每行、每列、两条对角线组成的五位数都是素数且各位数字和都等于 S，按 25 位数的字典序输出全部方案，无解输出 NONE。
// 思路：预处理 + 逐行 DFS。
// 1. 筛出所有各位数字和为 S 的五位数素数，并把它们的每一位前缀都标记出来。
// 2. 逐行填素数，每填一行就检查各列与两条对角线：拼出的前缀必须是某个合法素数的前缀，且当前数字和还有希望补足到 S。
// 3. 填到最后一行时前缀合法即意味着整列（整条对角线）是素数，收集答案后排序输出。
// 复杂度：搜索空间受前缀与数字和双重剪枝控制，实测很小
// 易错点：列和也要等于 S，所以某列已用的数字和必须满足 剩余行数 * 9 还能补足差额，否则要提前剪掉。
// 易错点：多组方案之间要输出一个空行，最后一组后面不要多输出空行。
#include <bits/stdc++.h>
using namespace std;
int S, head;
vector<int> allPrimes, byHead[10];
bool pref[100000];
int g[5][5];
vector<string> sols;
bool okPrefix(int val, int sum, int left){
    return pref[val] && sum <= S && S - sum <= 9 * left;
}
void dfs(int row){
    if(row == 5){
        string t;
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++) t += char('0' + g[i][j]);
        }
        sols.push_back(t);
        return;
    }
    int left = 4 - row;
    vector<int>& cand = (row == 0 ? byHead[head] : allPrimes);
    for(int p : cand){
        int d[5], q = p;
        for(int k = 4; k >= 0; k--){
            d[k] = q % 10;
            q /= 10;
        }
        bool ok = true;
        for(int j = 0; j < 5 && ok; j++){
            int val = 0, sum = 0;
            for(int i = 0; i < row; i++){
                val = val * 10 + g[i][j];
                sum += g[i][j];
            }
            ok = okPrefix(val * 10 + d[j], sum + d[j], left);
        }
        int v1 = 0, s1 = 0, v2 = 0, s2 = 0;
        for(int i = 0; i < row; i++){
            v1 = v1 * 10 + g[i][i];
            s1 += g[i][i];
            v2 = v2 * 10 + g[i][4 - i];
            s2 += g[i][4 - i];
        }
        if(!ok) continue;
        if(!okPrefix(v1 * 10 + d[row], s1 + d[row], left)) continue;
        if(!okPrefix(v2 * 10 + d[4 - row], s2 + d[4 - row], left)) continue;
        for(int j = 0; j < 5; j++) g[row][j] = d[j];
        dfs(row + 1);
    }
}
int main(){
    if(!(cin >> S >> head)) return 0;
    vector<bool> comp(100000, false);
    for(int i = 2; i * i < 100000; i++){
        if(!comp[i]){
            for(int j = i * i; j < 100000; j += i) comp[j] = true;
        }
    }
    for(int x = 10000; x < 100000; x++){
        if(comp[x]) continue;
        int s = 0, q = x;
        while(q){
            s += q % 10;
            q /= 10;
        }
        if(s != S) continue;
        allPrimes.push_back(x);
        byHead[x / 10000].push_back(x);
        int p = x;
        for(int k = 0; k < 5; k++){
            pref[p] = true;
            p /= 10;
        }
    }
    dfs(0);
    if(sols.empty()){
        cout << "NONE\n";
        return 0;
    }
    sort(sols.begin(), sols.end());
    for(int i = 0; i < (int)sols.size(); i++){
        if(i) cout << "\n";
        for(int r = 0; r < 5; r++) cout << sols[i].substr(r * 5, 5) << "\n";
    }
    return 0;
}
质数方阵

正文

一本通·提高篇的其它内容
