题意
构造一个(n)元有限域，若不存在输出-1，否则域中元素分别用(0, 1, 2, ldots, n - 1)表示，输出加法表和乘法表。
(n leq 343)。
题解
你我真的会域扩张吗？答：不会
首先，根据一些基础知识，有解当且仅当(n = p ^ d)，其中(p in mathbb{P})。
其次，根据域扩张的知识，我们要构造的( ext{GF}(p ^ d))一定是由素域( ext{GF}(p))有限扩张而来的。
考察在( ext{GF}(p))下的代数扩张，即假设存在一个( ext{GF}(p)[[x]])下的不可约多项式(f(x))，设(zeta)是这个多项式的一个根，那么( ext{GF}(p ^ d))中的所有元素可以唯一表示成一个多项式
（实际上是基(1, zeta, {zeta} ^ 2, ldots, {zeta} ^ {d - 1})的线性组合）
假设我们最后要输出的是这些多项式的加法表和乘法表，那么问题就转化为了找到一个合适的加法运算和乘法运算。
加法就是在域( ext{GF}(p)[[x]])下的多项式加法，乘法就是在域( ext{GF}(p)[[x]])下的多项式乘法。
但是多项式乘法会导致使用的基的大小变大，我们需要把基的大小缩到(d)。
考虑可以应用线性组合(f(zeta) = 0)。
对于一个多项式，加上或减去(k)倍的(f(zeta))（(k in ext{GF}(p)[[x]])），代入(zeta)求值不变。
那么对于一个多项式，如果次数超过了(d - 1)，可以将它对(f(zeta))取模，得到的结果是一个次数小于等于(d - 1)的多项式（即基的大小缩到了(d)），并且代入(zeta)后值和原多项式值相等。
现在考虑的是我们输出的是一个数表而不是多项式表，考虑到要把多项式(F)映射到数(f)，并且要求这个映射可逆。
如果有办法可以把(zeta)搞出来，那么当然可以直接将(F)映射到(F(zeta))上，这是个同构映射，显然可逆。
但是求(zeta)是不现实的，我们退而求其次，找一个要求不太高的可逆映射即可，比如把多项式(F)的系数看做数(f)在(p)进制下每一位的值，可以验证这是可行的。
复杂度(mathcal O(n ^ 2 {log} ^ 2 n))。
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> poly;
const int N = 360, M = 10;
const int R[7][8] = {
{1, 7, 11, 19, 37, 67, 131, 283}, // 2, 4, 8, 16, 32, 64, 128, 256
{1, 10, 34, 86, 250, -1, -1, -1}, // 3, 9, 27, 81, 243
{1, 27, 131, -1, -1, -1, -1, -1}, // 5, 25, 125
{1, 50, 345, -1, -1, -1, -1, -1}, // 7, 49, 343
{1, 122, -1, -1, -1, -1, -1, -1}, // 11, 121
{1, 171, -1, -1, -1, -1, -1, -1}, // 13, 169
{1, 292, -1, -1, -1, -1, -1, -1}, // 17, 289
};
int n, id[N], vis[N]; vector <int> pr;
void sieve () {
for (int i = 2; i < N; ++i) {
if (!vis[i]) {
id[i] = pr.size(), pr.push_back(i);
for (int j = i; j < N; j += i) {
vis[j] = i;
}
}
}
}
namespace GF {
int m, p, d, pl[M];
struct elem {
int x;
elem (int _x = 0) : x(_x) {}
elem compress (const poly &r) {
x = 0;
for (int i = d - 1; ~i; --i) {
x = x * p + r[i];
}
return *this;
}
poly expand (elem e) {
poly r(d);
for (int i = 0; i < d; ++i) {
r[i] = e.x % p, e.x /= p;
}
return r;
}
elem operator + (const elem &o) {
poly F = expand(*this), G = expand(o);
for (int i = 0; i < d; ++i) {
F[i] = (F[i] + G[i]) % p;
}
return compress(F);
}
elem operator * (const elem &o) {
poly F = expand(*this), G = expand(o), H(d + d, 0);
for (int i = 0; i < d; ++i) {
for (int j = 0; j < d; ++j) {
H[i + j] = (H[i + j] + F[i] * G[j]) % p;
}
}
for (int i = (d - 1) << 1; i > d - 1; --i) {
H[i] = -H[i] % p, H[i] += H[i] >> 31 & p;
for (int j = 1; j <= d; ++j) {
H[i - j] = (H[i - j] + H[i] * pl[d - j]) % p;
}
}
return compress(H);
}
} ;
void get_poly () {
for (int i = 0, x = R[id[p]][d - 1]; i <= d; ++i) {
pl[i] = x % p, x /= p;
}
}
} using namespace GF;
int main () {
sieve();
cin >> n, m = n, p = vis[n];
for (int x = n; x != 1; x /= p, ++d) {
if (x % p != 0) {
n = 1;
break;
}
}
if (n == 1) {
puts("-1");
} else {
puts("0");
get_poly();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
printf("%d%c", ((elem)i + (elem)j).x, j < n - 1 ? ' ' : '
');
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
printf("%d%c", ((elem)i * (elem)j).x, j < n - 1 ? ' ' : '
');
}
}
}
return 0;
}
/*
4 : x ^ 2 + x + 1 (111)2 = 7
8 : x ^ 3 + x + 1 (1011)2 = 11
9 : x ^ 2 + 1 (101)3 = 10
25 : x ^ 2 + 2 (102)5 = 27
27 : x ^ 3 + 2x + 1 (1021)3 = 34
81 : x ^ 4 + x + 2 (10012)3 = 86
121: x ^ 2 + 1 (101)11 = 122
125: x ^ 3 + x + 1 (1011)5 = 131
169: x ^ 2 + 2 (102)13 = 171
128: x ^ 7 + x + 1 (10000011)2 = 131
243: x ^ 5 + 2x + 1 (1000021)3 = 250
256: x ^ 8 + x ^ 4 + x ^ 3 + x + 1 (100011011)2 = 283
343: x ^ 3 + 2 (1002)7 = 345
*/