usaco-4.3.2 素数方阵

形式化题目

在 $5 \times 5$ 的方格中填入数字 $0 \sim 9$ ，把每行、每列、两条对角线都读成五位数：

5 行按从左到右读：第 $r$ 行是 $g_{r,0} g_{r,1} g_{r,2} g_{r,3} g_{r,4}$ ；
5 列按从上到下读：第 $c$ 列是 $g_{0,c} g_{1,c} g_{2,c} g_{3,c} g_{4,c}$ ；
主对角线从左到右读 $g_{0,0} g_{1,1} g_{2,2} g_{3,3} g_{4,4}$ ；
副对角线也按从左到右读，即 $g_{4,0} g_{3,1} g_{2,2} g_{1,3} g_{0,4}$ 。

这 12 个数必须同时满足两条：

都是素数，且首位不为 $0$ （即都落在 $[10000, 99999]$ ，所以四个角都非零）；
各位数字之和都等于输入的 $S$ 。

输入另给左上角固定值 $g_{0,0} = D$ 。求全部方案；把每个方案的 25 个数字按行拼接成一个 25 位数，按该数从小到大排序输出，方案之间空一行；无解输出一行 NONE。

形式化地，令 $\operatorname{dig}$ 表示五位数拆成数字的序列， $\operatorname{dsum}(x)$ 为其数字和， $\mathcal{P} = \{\, p \text{ 是素数} : 10000 \leqslant p < 100000,\ \operatorname{dsum}(p) = S \,\}$ ，则要求

\text{行}_r,\ \text{列}_c,\ \text{两条对角线} \in \mathcal{P},\qquad g_{0,0} = D .

副对角线不是"右上到左下"。 题面说两条对角线都从左到右读，所以副对角线左端是 左下角 $g_{4,0}$ 、右端是右上角 $g_{0,4}$ 。这一点直接决定输出里第 5、1 行的数字，写反了样例仍能全对、真实数据却全错（见下）。

正解

思路

朴素做法。 直接按候选素数枚举 5 行：预处理出 $S$ 的候选集 $\mathcal{P}$ 后，枚举 $5$ 个素数填行，再检查 5 列与两条对角线。 $\mathcal{P}$ 的规模在 $S \approx 23$ 时高达 $757$ ， $757^5 \approx 2.5 \times 10^{14}$ ，完全不可行。逐格 DFS 更差： $10^{25}$ 个状态。

瓶颈的根源是"把 12 条线当成彼此独立"。真正稠密的是交叉点：两条对角线共享中心点 $(2,2)$ ，于是

主对角线定首值 $D$ → 定出 $g_{2,2}$ 与 $g_{4,4}$ ；
副对角线必须过同一个中心点 → 定出 $g_{4,0}$ 、 $g_{0,4}$ ，且 $g_{0,4}$ 也是第 0 行的末位；
四角与中心全部落定后，四条边框线（第 0 行、第 4 行、第 0 列、第 4 列）各自的两个端点都已知。

一条五位素数若首末两位都固定，候选往往只剩个位数几个——我用 headTail[h][t] 把 $\mathcal{P}$ 按首末位分桶，边框候选直接查表，不必扫全表。

关键的一步：内部 4 个格子不用枚举。 边框的四个"肩部"数字一旦选定，内部四格被行/列数位和唯一确定。把网格的符号约定写出来：

text

1
2
3
4
5
6          c0    c1    c2    c3    c4
   r0  [  D    b     c     d    x04 ]
   r1  [ g11  e2    h    f2    i  ]
   r2  [  l    m    mid    o    n  ]
   r3  [  q   f4    r    e4    s  ]
   r4  [ x40   v     w     x   x44 ]

其中主对角线数是 $D\,e_2\,mid\,e_4\,x44$ ，副对角线数是 $x40\,f_4\,mid\,f_2\,x04$ （左端 $x40$ 在左下角）。四个角 $D, x04, x40, x44$ 与中心 $mid$ 由两条对角线锁定；第 0 行、第 4 行、第 0 列、第 4 列是四条边框线。把上面的符号代入数位和，得

g_{2,1} = S - b - e_2 - f_4 - v,\qquad g_{2,3} = S - d - f_2 - e_4 - x,

g_{1,2} = S - g_{1,1} - e_2 - f_2 - i,\qquad g_{3,2} = S - q - f_4 - e_4 - s .

前两式只依赖"第 0 行、第 4 行"的肩部；后两式再依赖"第 0 列、第 4 列"的肩部。于是枚举收缩成两层：外层「主对角线 → 副对角线」先锁定四角与中心，内层「第 0 行 → 第 4 行 → 第 0 列 → 第 4 列」铺满外框，每一层都用 headTail 把候选压到常数级，内部四格全部由减法算出。最后剩下的两个"和"约束（第 2 行、第 2 列）以及 4 条内部线的素数判定做校验即可。

为什么最后只剩第 2 行、第 2 列要查数位和？ 12 条线里，第 1 行、第 3 行、第 1 列、第 3 列的数字和被上面的反推式构造出来，必然等于 $S$ ；第 0/4 行、第 0/4 列来自 $\mathcal{P}$ ；两条对角线来自 $\mathcal{P}$ 。只剩第 2 行 $g_{2,0}\dots g_{2,4}$ 与第 2 列 $g_{0,2},g_{1,2},g_{2,2},g_{3,2},g_{4,2}$ 是"顺带凑出来"的，所以要逐个查它们是否落在 $\mathcal{P}$ 里。把校验写成"是否在 $\mathcal{P}$ 中"，一条语句同时覆盖了素数、首位非零和数位和三个条件。

输出顺序。 题目只要求按 25 位数升序，所以把每个解拼成 25 位字符串后统一 sort 再输出，不必让搜索顺序去迎合字典序。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:07
# update_at: 2026-10-08 07:07

import sys
from collections import defaultdict

LIMIT = 100000   # 五位素数都小于十万，筛表大小取到这里

type Layouts = list[str]        # 每个解按行拼成的 25 位数字串
type Digits = dict[int, tuple[int, ...]]  # 候选素数 -> 它的五位数字
type Grouped = dict[tuple[int, int], list[int]]  # (首位, 末位) -> 候选素数


def sieve(n: int) -> bytearray:
    """返回长度为 n 的标记表，第 p 位为 1 表示 p 是素数。"""
    flag = bytearray([1]) * n
    flag[0] = flag[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if flag[i]:
            flag[i * i :: i] = bytearray(len(range(i * i, n, i)))
    return flag


def mk(a: int, b: int, c: int, d: int, e: int) -> int:
    """把五个数位按从左到右拼成五位数，用来直接查合法线集合。"""
    return ((((a * 10 + b) * 10 + c) * 10 + d) * 10 + e)


def layouts(S: int, D: int) -> Layouts:
    """枚举全部解：每条线都是数位和恰为 S 的五位素数，左上角固定为 D。

    先定两条共享中心点的对角线（锁死四角与中心），再定四条边框线；
    内部四格由行 1/行 3/列 1/列 3 的数位和反推，最后校验第 2 行、第 2 列。
    """
    prime = sieve(LIMIT)
    cand = [p for p in range(10000, LIMIT) if prime[p] and sum(map(int, str(p))) == S]
    if not cand:
        return []
    valid = set(cand)  # 一条线合法 ⇔ 它本身是候选素数（首位非零、数位和 = S 一并满足）
    dig: Digits = {p: tuple(int(ch) for ch in str(p)) for p in cand}
    head_tail: Grouped = defaultdict(list)
    for p in cand:
        head_tail[p // 10000, p % 10].append(p)

    res: Layouts = []
    for d1 in cand:
        if dig[d1][0] != D:
            continue                          # 主对角线首位就是左上角
        e2, mid, e4 = dig[d1][1], dig[d1][2], dig[d1][3]
        for d2 in cand:
            if dig[d2][2] != mid:
                continue                      # 副对角线必须穿过同一个中心点
            # 副对角线也按从左到右读：第 1 位是左下角，第 5 位是右上角
            x40, f4, f2, x04 = dig[d2][0], dig[d2][1], dig[d2][3], dig[d2][4]
            x44 = dig[d1][4]                  # 右下角
            for r0 in head_tail[D, x04]:      # 第 0 行：首尾为左上角、右上角
                b, c, d = dig[r0][1], dig[r0][2], dig[r0][3]
                for r4 in head_tail[x40, x44]:  # 第 4 行：首尾为左下角、右下角
                    v, w, x = dig[r4][1], dig[r4][2], dig[r4][3]
                    m = S - b - e2 - f4 - v   # 列 1 的数位和定出 g[2][1]
                    o = S - d - f2 - e4 - x   # 列 3 的数位和定出 g[2][3]
                    # 这两格由和推出，必须在 0~9 内，且填好后列 1、列 3 都是合法线
                    mid_ok = (
                        0 <= m <= 9
                        and 0 <= o <= 9
                        and mk(b, e2, m, f4, v) in valid
                        and mk(d, f2, o, e4, x) in valid
                    )
                    if not mid_ok:
                        continue
                    for c0 in head_tail[D, x40]:  # 第 0 列：首尾为左上角、左下角
                        g11, l, q = dig[c0][1], dig[c0][2], dig[c0][3]
                        for c4 in head_tail[x04, x44]:  # 第 4 列：首尾为右上角、右下角
                            i, n, s = dig[c4][1], dig[c4][2], dig[c4][3]
                            h = S - g11 - e2 - f2 - i  # 行 1 的数位和定出 g[1][2]
                            r = S - q - f4 - e4 - s    # 行 3 的数位和定出 g[3][2]
                            # 同理：这两格必须落在 0~9，填好后行 1、行 3 都要是合法线
                            edge_ok = (
                                0 <= h <= 9
                                and 0 <= r <= 9
                                and mk(g11, e2, h, f2, i) in valid
                                and mk(q, f4, r, e4, s) in valid
                            )
                            if not edge_ok:
                                continue
                            # 最后两个和约束：第 2 行、第 2 列也必须是合法线
                            row2_ok = mk(l, m, mid, o, n) in valid
                            col2_ok = row2_ok and mk(c, h, mid, r, w) in valid
                            if not col2_ok:
                                continue
                            res.append(
                                f"{D}{b}{c}{d}{x04}"
                                f"{g11}{e2}{h}{f2}{i}"
                                f"{l}{m}{mid}{o}{n}"
                                f"{q}{f4}{r}{e4}{s}"
                                f"{x40}{v}{w}{x}{x44}"
                            )
    return res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    S, D = next(data), next(data)  # 数位和、左上角固定数字

    ans = layouts(S, D)
    if not ans:
        print("NONE")
        return
    ans.sort()  # 与 25 位数升序一致
    out: list[str] = []
    for k, layout in enumerate(ans):
        if k:
            out.append("")  # 两组方案之间空一行
        out += [layout[r * 5 : r * 5 + 5] for r in range(5)]
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:07
 * update_at: 2026-10-08 07:07
 */
// usaco-4.3.2 素数方阵（ROJ 2070）
// 5x5 网格的 5 行、5 列、2 条对角线都是数位和恰为 S 的五位素数，左上角固定为 D。
//
// 关键：两条对角线只共享中心点，先把它们定下来就锁死四角与中心；四条边框线
// 于是各有两个端点已知。边框上四个"肩部"数字 b/v/d/x、g/i/q/s 一旦选定，
// 内部 4 个格子的值就被行 1、行 3、列 1、列 3 的数位和唯一确定，
// 只剩第 2 行、第 2 列两个和约束作为校验——搜索因此坍缩成两层小枚举。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXV = 100000;                        // 五位素数 < 100000
const int PW[5] = {10000, 1000, 100, 10, 1};    // 第 pos 位权重（0 = 万位）

bool isPrime[MAXV];            // 埃氏筛结果
int g[5][5];                   // 网格，g[r][c]：第 r 行第 c 列，0 行在最上
int S;                         // 各条线共同的数位和
int D;                         // 左上角固定数字
vector<int> cand;              // 数位和恰为 S 的五位素数，升序
vector<int> headTail[10][10];  // headTail[h][t]：首位 h、末位 t 的候选素数
vector<string> ans;            // 所有解，按行拼成的 25 位数字串

int digit(int x, int pos) {
    // 取五位数的第 pos 位，0 = 万位 … 4 = 个位
    return x / PW[pos] % 10;
}

bool okValue(int v) {
    // 合法线：五位素数且数位和恰为 S（首位非零由 v >= 10000 保证）
    if (v < 10000 || !isPrime[v]) return false;
    int sum = 0;
    for (int k = 0; k < 5; k++) sum += digit(v, k);
    return sum == S;
}

int make5(int a, int b, int c, int d, int e) {
    return a * 10000 + b * 1000 + c * 100 + d * 10 + e;
}

int main() {
    for (int i = 2; i < MAXV; i++) isPrime[i] = true;
    for (int i = 2; i * i < MAXV; i++)
        if (isPrime[i])
            for (int j = i * i; j < MAXV; j += i) isPrime[j] = false;

    if (scanf("%d %d", &S, &D) != 2) return 0;

    for (int p = 10000; p < MAXV; p++) {
        if (!isPrime[p]) continue;
        int sum = 0;
        for (int k = 0; k < 5; k++) sum += digit(p, k);
        if (sum == S) cand.push_back(p);
    }
    if (cand.empty()) { printf("NONE\n"); return 0; }
    for (size_t t = 0; t < cand.size(); t++)
        headTail[cand[t] / 10000][cand[t] % 10].push_back(cand[t]);

    for (size_t i1 = 0; i1 < cand.size(); i1++) {
        int d1 = cand[i1];                          // 主对角线，首位必须等于 D
        if (digit(d1, 0) != D) continue;
        int mid = digit(d1, 2);                     // 中心点 (2,2)
        int e3 = digit(d1, 1), e5 = digit(d1, 3);   // 主对角线第 2、4 位
        for (size_t i2 = 0; i2 < cand.size(); i2++) {
            int d2 = cand[i2];                      // 副对角线，必须穿过中心点
            if (digit(d2, 2) != mid) continue;
            // 副对角线也按从左到右读：左端是左下角，故第 1 位 = 左下角、第 5 位 = 右上角
            int x40 = digit(d2, 0), x04 = digit(d2, 4);  // 左下、右上角
            int x44 = digit(d1, 4);                      // 右下角
            int f4 = digit(d2, 1), f2 = digit(d2, 3);    // 副对角线第 2、4 位（g[3][1]、g[1][3]）

            // 第 0、4 行：首尾即左上/右上、左下/右下角
            vector<int> &r0s = headTail[D][x04], &r4s = headTail[x40][x44];
            // 第 0、4 列：首尾即左上/左下角、右上/右下角
            vector<int> &c0s = headTail[D][x40], &c4s = headTail[x04][x44];

            for (size_t a = 0; a < r0s.size(); a++) {
                int r0 = r0s[a];
                int b = digit(r0, 1), c = digit(r0, 2), d = digit(r0, 3);
                for (size_t ii = 0; ii < r4s.size(); ii++) {
                    int r4 = r4s[ii];
                    int v = digit(r4, 1), w = digit(r4, 2), x = digit(r4, 3);
                    // 列 1、列 3 的数位和分别定出 g[2][1]、g[2][3]
                    int m = S - b - e3 - f4 - v;
                    int o = S - d - f2 - e5 - x;
                    if (m < 0 || m > 9 || o < 0 || o > 9) continue;
                    int col1 = make5(b, e3, m, f4, v);
                    if (!okValue(col1)) continue;
                    int col3 = make5(d, f2, o, e5, x);
                    if (!okValue(col3)) continue;

                    for (size_t bb = 0; bb < c0s.size(); bb++) {
                        int c0 = c0s[bb];
                        int gg = digit(c0, 1), l = digit(c0, 2), q = digit(c0, 3);
                        for (size_t dd = 0; dd < c4s.size(); dd++) {
                            int c4 = c4s[dd];
                            int i = digit(c4, 1), n = digit(c4, 2), s = digit(c4, 3);
                            // 行 1、行 3 的数位和分别定出 g[1][2]、g[3][2]
                            int h = S - gg - e3 - f2 - i;
                            int r = S - q - f4 - e5 - s;
                            if (h < 0 || h > 9 || r < 0 || r > 9) continue;
                            if (!okValue(make5(gg, e3, h, f2, i))) continue;   // 第 1 行
                            if (!okValue(make5(q, f4, r, e5, s))) continue;    // 第 3 行
                            // 第 2 行 / 第 2 列是最后两个和约束，顺带查素数
                            if (!okValue(make5(l, m, mid, o, n))) continue;    // 第 2 行
                            if (!okValue(make5(c, h, mid, r, w))) continue;    // 第 2 列

                            g[0][0] = D;    g[0][1] = b;  g[0][2] = c;   g[0][3] = d;   g[0][4] = x04;
                            g[1][0] = gg;   g[1][1] = e3; g[1][2] = h;   g[1][3] = f2;  g[1][4] = i;
                            g[2][0] = l;    g[2][1] = m;  g[2][2] = mid; g[2][3] = o;   g[2][4] = n;
                            g[3][0] = q;    g[3][1] = f4; g[3][2] = r;   g[3][3] = e5;  g[3][4] = s;
                            g[4][0] = x40;  g[4][1] = v;  g[4][2] = w;   g[4][3] = x;   g[4][4] = x44;
                            string cur;
                            for (int rr = 0; rr < 5; rr++)
                                for (int cc = 0; cc < 5; cc++) cur += char('0' + g[rr][cc]);
                            ans.push_back(cur);
                        }
                    }
                }
            }
        }
    }

    if (ans.empty()) { printf("NONE\n"); return 0; }
    sort(ans.begin(), ans.end());   // 按 25 位数升序
    for (size_t i = 0; i < ans.size(); i++) {
        if (i) printf("\n");
        for (int r = 0; r < 5; r++) {
            for (int c = 0; c < 5; c++) putchar(ans[i][r * 5 + c]);
            putchar('\n');
        }
    }
    return 0;
}

复杂度

预处理：埃氏筛 $O(M \log\log M)$ ， $M = 10^5$ ；分桶 $O(|\mathcal{P}|)$ 。
搜索：两层枚举。外层是「主对角线候选 $\times$ 过同一中心点的副对角线候选」的配对，真实数据上为 $785 \sim 7797$ 对（ $|\mathcal{P}| \approx 143 \sim 757$ ）；内层四个 for 在 headTail 的分桶里走，最内层循环体的总执行次数为 $3.3 \times 10^4 \sim 5.3 \times 10^6$ 。 C++ 十个真实数据点全部 $\leqslant 0.04$ s（限时 1000 ms），峰值内存 8.3 MB。
空间：筛表 $10^5$ 字节、候选与分桶表 $O(|\mathcal{P}|)$ 、答案 $O(\text{解数} \times 5)$ 。最大解数 152（ $S=23, D=3$ ），空间为常数级。
与 C++ 解法的关系：main.py 与 main.cpp 用完全相同的搜索顺序与剪枝， Python 最大点约 1.2 s——算法同阶，只是常数更大，不存在"为过时限而降级算法"的情况。

总结

交叉点就是剪枝点：两条对角线共享中心、又各自带着两个角，先把它们定下来， 12 条线里立刻有 6 条被完全确定、4 条只剩"中间三格"未知。选对枚举对象比任何常数优化都有效——本题的关键不是"填格子"，而是"先填约束最稠密的那两条线"。
能算出来的就别枚举：内部四格由数位和反推，搜索深度从 25 格塌到外框 16 格 + 4 个减法。这是构造题里常见的手法：把一部分变量的取值变成前若干层变量的仿射函数。
把多重条件收进一张哈希表：valid = set(cand) 让"是素数且数位和 = S 且五位" 退化成一次 in，校验代码短且不易漏条件。
对角线的读法要看清方向：题面明确两条对角线都从左到右读，副对角线的左端是左下角。写成"右上到左下"时样例恰好三条解全都相同（ $S=11,D=1$ 的例子里正副对角线首末对称），于是样例全对、10 个真实点全错——这是本题最容易踩的坑。
无解时输出单独一行 NONE，注意不要输出多余空行。

图示解析（对角线与外框的依赖）

flowchart LR
  D1["主对角线 D e2 mid e4 x44"] --> C["中心 (2,2) = mid"]
  D2["副对角线 x40 f4 mid f2 x04"] --> C
  C --> R0["第 0 行: 首尾 D, x04"]
  C --> R4["第 4 行: 首尾 x40, x44"]
  C --> C0["第 0 列: 首尾 D, x40"]
  C --> C4["第 4 列: 首尾 x04, x44"]
  R0 --> IN["内部 4 格由数位和反推"]
  R4 --> IN
  C0 --> IN
  C4 --> IN
  IN --> CHK["校验第 2 行 / 第 2 列"]