题解 - [Luogu P3923] 大学数学题

发表于 更新于 分类于 ， 本文字数： 1.7k 阅读时长 ≈ 6 分钟

题目链接

原始题面

题目背景

琪露诺：我知道了！答案一定是 1!

露米娅：什么鬼啊 (汗), 你还是再想想去吧... 我先把最后一道题给你，这是一道大学数学题哦

题目描述

露米娅：大妖精想构造一个 \(n\) 元有限域，元素用 \(0 \sim n - 1\) 的整数表示 有限域需要满足以下条件

  1. 有加法单位元 \(o\), 满足对于任意元素 \(a\), \(o + a = a + o = a\)
  2. 对于任意元素 \(a\), 存在加法逆元 \(a^{-1}\), 使得 \(a + a^{-1} = a^{-1} + a = o\)
  3. 有不同于加法单位元 \(o\) 的乘法单位元 \(i\), 满足对于任意元素 \(a\), \(i \times a = a \times i = a\)
  4. 对于任意非加法单位元元素 \(a\), 存在乘法逆元 \(a^{-1}\), 使得 \(a \times a^{-1} = a^{-1} \times a = i\)
  5. 对于任意元素 \(x\), \(y\), 有加法交换律，即 \(x + y = y + x\)
  6. 对于任意元素 \(x\), \(y\), 有乘法交换律，即 \(x \times y = y \times x\)
  7. 对于任意元素 \(x\), \(y\), \(z\), 有加法结合律，即 \((x + y) + z = x + (y + z)\)
  8. 对于任意元素 \(x\), \(y\), \(z\), 有乘法结合律，即 \((x \times y) \times z = x \times (y \times z)\)
  9. 对于任意元素 \(x\),\(y\),\(z\), 有乘法分配律，即 \((x + y) \times z = x \times z + y \times z\)

大妖精当然会做啦，但是他想考考你

在输出中加法单位元 \(o\) 即为 \(0\), 乘法单位元 \(i\) 即为 \(1\)

输入输出格式

输入格式

一个正整数 \(n\)

\(2 \leq n \leq 350\)

输出格式

第一行输出一个正整数 \(k\), 若存在 \(n\) 元有限域则 \(k = 0\), 否则 \(k = -1\)

若 \(k = 0\) 则

  1. 接下来 \(n\) 行输出一个 \(n\) 元有限域的加法表，第 \(i + 1\) 行第 \(j + 1\) 列上的数代表有限域中 \(i + j\) 的运算结果
  2. 接下来 \(n\) 行输出一个 \(n\) 元有限域的乘法表，第 \(i + 1\) 行第 \(j + 1\) 列上的数代表有限域中 \(i \times j\) 的运算结果

共输出 \(n \times 2 + 1\) 行

upd1:SPJ 非常严格，请不要在行末输出多余空格

(答案文件末尾的换行还是会自动忽略的)

upd2: 正解文件比较大，洛谷可能会一直 judging...

如果遇到这种情况请直接提交源代码

输入输出样例

输入样例 #1

1
2

输出样例 #1

1
2
3
4
5
0
0 1
1 0
0 0
0 1

说明

测试点 [\(n\) 的范围] 特殊性质
1 [\(n = 3\)] \(n\) 是质数
2 [\(n = 4\)] \(n\) 是 2 的整数次方
3 [\(n = 6\)] 无
4 [\(n = 8\)] \(n\) 是 2 的整数次方
5 [\(n = 9\)] 无
6 [\(n = 19\)] \(n\) 是质数
7 [\(n = 89\)] \(n\) 是质数
8 [\(n = 181\)] \(n\) 是质数
9 [\(n = 233\)] \(n\) 是质数
10 [\(n = 25\)] \(n\) 是质数的平方
11 [\(n = 121\)] \(n\) 是质数的平方
12 [\(n = 169\)] \(n\) 是质数的平方
13 [\(n = 27\)] 无
14 [\(n = 143\)] 无
15 [\(n = 128\)] \(n\) 是 2 的整数次方
16 [\(n = 81\)] 无
17 [\(n = 125\)] 无
18 [\(n = 243\)] 无
19 [\(n = 256\)] \(n\) 是 2 的整数次方
20 [\(n = 343\)] 无

题意简述

构造一个 \(n\) 元有限域 \(\mathbb{E}_n\), 不存在时输出 -1

解题思路

抽代题是吧... 我直接进行一个定理的摆

我们称没有真子域的域为素域

首先域的特征要么为 \(0\), 要么为素数 \(p\), 进一步我们有

定理 - 1 任意一个域 \(\mathbb{F}\) 都含且仅含一个素域

  • 当 \(\operatorname{char}(\mathbb{F})=0\) 时，\(\mathbb{F}\) 的素域与 \(\mathbb{Q}\) 同构
  • 当 \(\operatorname{char}(\mathbb{F})=p\) 时，\(\mathbb{F}\) 的素域与 \(\mathbb{Z}_p\) 同构

进一步，两个域的特征相同当且仅当其素域同构

证明

令

\[ \{\mathbb{F}_i|\mathbb{F}_i\leqslant \mathbb{F},i\in I\} \]

为 \(\mathbb{F}\) 全体子域构成的集合，显然其交集 \(\mathbb{P}\) 非空，且

  • \(\mathbb{P}\leqslant\mathbb{F}\)
  • \(\mathbb{P}\) 为 \(\mathbb{F}\) 的唯一素域

我们构造如下映射

\[ \begin{aligned} \varphi:\mathbb{Z}&\to\mathbb{P}\\ m&\mapsto me \end{aligned} \]

其中 \(e\) 为 \(\mathbb{F}\) 的幺元，显然 \(\varphi\) 为同态映射

  • 若 \(\operatorname{char}(\mathbb{F})=0\), 则 \(\ker\varphi=\{0\}\), 令

    \[ R_e:=\{me|m\in\mathbb{Z}\} \]

    由同态基本定理，\(R_e\cong\mathbb{Z}\), \(R_e\) 为一整环，从而其分式域 \(\mathbb{F}_e\cong\mathbb{Q}\)

    显然

    • \(\mathbb{F}_e\leqslant\mathbb{F}\)
    • \(\mathbb{F}\) 任一素域均包含 \(\mathbb{F}_e\)

    故 \(\mathbb{F}_e\) 即为 \(\mathbb{F}\) 同构于 \(\mathbb{Q}\) 的素域

  • 若 \(\operatorname{char}(\mathbb{F})=p\), 则 \(\ker\varphi=\{p\}\), 令

    \[ R_e:=\{0,e,2e,...,(p-1)e\} \]

    由同态基本定理，\(R_e\cong\mathbb{Z}_p\), 而 \(\mathbb{Z}_p\) 显然为素域，故 \(R_e\) 即为 \(\mathbb{F}\) 同构于 \(\mathbb{Z}_p\) 的素域

令 \(n\) 元有限域为 \(\mathbb{E}_n\), 显然其特征必为素数，故 \(n=6\) 和 \(n=143\) 的情况直接输出 -1 即可

记 \(\mathbb{E}_n\) 的素域为 \(\mathbb{F}_p\), 其中 \(p\) 为 \(\mathbb{E}_n\) 的特征

定理 - 2 \(\forall p\in\text{Prime}^+,m\in\mathbb{N}^+\), \(p^m\) 阶有限域必存在且在 \(\mathbb{F}_p\)- 同构意义下是唯一的

证明

令 \(f(x)=x^{p^m}-x\in\mathbb{F}_p[x]\), 作 \(\mathbb{F}_p\) 关于 \(f(x)\) 的分裂域

\[ \mathbb{E}=\mathbb{F}_p(\alpha_0,\alpha_1,\dots,\alpha_{p^m}) \]

其中 \(\alpha_0,\alpha_1,\dots,\alpha_{p^m}\) 为 \(f(x)\) 在 \(\mathbb{E}\) 中的根

又由 \(\operatorname{char}(\mathbb{F}_p)=p\) 知，\(f'(x)=-1\), 从而 \((f(x),f'(x))=1\), 即 \(f(x)\) 无重根

令 \(\mathbb{L}=\{\alpha_0,\alpha_1,\dots,\alpha_{p^m}\}\), 则 \(\forall\alpha_i,\alpha_j\in\mathbb{L}\)

  • \[ (\alpha_i-\alpha_j)^{p^m}=\alpha_i-\alpha_j\in\mathbb{L} \]
  • \[ \left(\frac{\alpha_i}{\alpha_j}\right)^{p^m}=\frac{\alpha_i}{\alpha_j}\in\mathbb{L},~(\alpha_j\ne 0) \]

故 \(\mathbb{L}\leqslant\mathbb{E}\)

又 \(\mathbb{F}_p\leqslant\mathbb{L}\), 故 \(\mathbb{E}\leqslant\mathbb{L}\)

从而 \(\mathbb{E}=\mathbb{L}\), \(|\mathbb{E}|=|\mathbb{L}|=p^m\)

故其他数据点均可以构造

首先，我们知道，\(\forall p\in\text{Prime}^+\), \((\mathbb{Z}_p,+,\cdot)\) 为一个域

接下来我们尝试构造素数幂次阶的有限域

定理 - 3 令 \(p(x)\) 为 \(\mathbb{F}_p[x]\) 中一 \(m\) 次首 1 不可约多项式 (\(m\geqslant 1\)), 则

\[ \mathbb{F}_p[x]/\lang p(x)\rang=\left\{\sum_{i=0}^{m-1}a_ix^i+\lang p(x)\rang\bigg|a_i\in\mathbb{F}_p,~i=0,1,...m-1\right\} \]

为一阶为 \(p^m\) 的有限域

证明

易得 \(\lang p(x)\rang\) 为 \(\mathbb{F}_p[x]\) 的极大理想，从而 \(\mathbb{F}_p[x]/\lang p(x)\rang\) 为一域

由 \(\mathbb{F}_p\) 为阶为 \(p\) 的素域，易得

\[ |\mathbb{F}_p[x]/\lang p(x)\rang|=p^m \]

我们将 \(\mathbb{F}_p[x]/\lang p(x)\rang\) 中的多项式看作 \(p\) 进制数，不难发现这个操作是同构映射，故这题我们就做完了

代码参考

Show code

Luogu_P3923view raw
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
"""
@Author: Tifa
@Description: From <https://github.com/Tiphereth-A/CP-archives>
!!! ATTENEION: All the context below is licensed under a
  GNU Affero General Public License, Version 3.
  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
"""
import numpy as np
primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
          61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
          149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
          239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
          347, 349)
prime_polys = {
    4: np .array([1, 1, 1], dtype=int),
    8: np .array([1, 0, 1, 1], dtype=int),
    9: np .array([1, 0, 1], dtype=int),
    16: np .array([1, 0, 0, 1, 1], dtype=int),
    25: np .array([1, 1, 1], dtype=int),
    27: np .array([1, 2, 1, 1], dtype=int),
    81: np .array([1, 0, 1, 1, 1], dtype=int),
    121: np .array([1, 1, 1], dtype=int),
    125: np .array([1, 0, 1, 1], dtype=int),
    128: np .array([1, 0, 0, 0, 0, 0, 1, 1], dtype=int),
    143: np .array([1, 1, 1], dtype=int),
    169: np .array([1, 1, 2], dtype=int),
    243: np .array([1, 0, 1, 3, 1, 1], dtype=int),
    256: np .array([1, 0, 0, 1, 0, 1, 0, 1, 1], dtype=int),
    343: np .array([1, 3, 1, 1], dtype=int)
}
polys = [np .array([0], dtype=int)]


def add(p, i, j):
    return np .polyval(np .polyadd(polys[i], polys[j]) % p, p)


def mul(p, k, i, j):
    conv = np .convolve(polys[i], polys[j])
    pp = prime_polys[p ** k]
    if conv .shape[0] >= pp .shape[0]:
        conv = np .polydiv(conv, pp)[1]
    return int(np .polyval(conv % p, p))


n = int(input())
prime = 0
cnt = 0
for i in primes:
    if n % i == 0:
        nn = n
        prime = i
        while nn % i == 0:
            nn = nn // i
            cnt = cnt + 1
        if nn != 1:
            print(-1)
            exit()
        break
print(0)
if cnt == 1:
    for i in range(0, n):
        for j in range(0, n):
            print((i + j) % n, end=(''if j == n - 1 else ' '))
        print()
    for i in range(0, n):
        for j in range(0, n):
            print((i * j) % n, end=(''if j == n - 1 else ' '))
        print()
else:
    for i in range(1, n):
        poly_i = []
        while i != 0:
            poly_i .append(i % prime)
            i = i // prime
        poly_i .reverse()
        polys .append(np .array(poly_i, dtype=int))
    res = np .zeros((n, n), dtype=int)
    for i in range(0, n):
        for j in range(i, n):
            res[i][j] = res[j][i] = add(prime, i, j)
    for i in range(0, n):
        for j in range(0, n):
            print(res[i][j], end=(''if j == n - 1 else ' '))
        print()
    for i in range(0, n):
        for j in range(i, n):
            res[i][j] = res[j][i] = mul(prime, cnt, i, j)
    for i in range(0, n):
        for j in range(0, n):
            print(res[i][j], end=(''if j == n - 1 else ' '))
        print()