15011418730 LV 7 @ 2025-8-24 21:54:07

自动搬运

来自洛谷，原作者为

	Drystynt Cokernel

搬运于2025-08-24 21:54:07，当前版本为作者最后更新于2021-01-04 11:41:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Updated On 2021/9/19. 笔者学了抽象代数之后，做了一些补充，同时修改了一些对专业术语的措辞。增加的地方加了P.S.。P.S.的部分比较难懂，若无法理解可以不看它们。不看P.S.的部分对全文理解不会有过多的影响。

一个有趣的抽象代数题。

开始我也是没有思路，于是就开始碰碰运气。我们先试一下-1:

case 6:case 143:cout<<"-1";break;

发现自己得了10分。对的是哪两个点呢？

第3和第14个，此时 $n=6$ 或 $143$ 。注意到其他的数都是素数的不小于1的整数幂，而这两个不是，于是猜想：不存在大于1个素因子的合数之元的有限域。

于是我们不管这些合数了，只看素数的不小于1的整数幂。先观察素数：因为素数的完全剩余系与简化剩余系是相同的，我们直接把两个数相加并模这个素数即可。[P.S. 这里在有限域中即为： $GF(p)=\mathbb{Z}/p\mathbb{Z}.$ ]

case 3:case 19:case 89:case 181:case 233:
{
   cout<<"0"<<endl;
   for(int i=0;i<n;i++)
   {
     for(int j=0;j<n;j++)
     {
        cout<<(i+j)%n;
        if(j==n-1)continue;
        else cout<<' ';
     }
     cout<<endl;
   }
   for(int i=0;i<n;i++)
   {
     for(int j=0;j<n;j++)
     {
        cout<<(i*j)%n;
        if(j==n-1)continue;
        else cout<<' ';
     }
     cout<<endl;
   }
}break;

于是就 $35$ 分到手了

后面怎么办呢？

我试了一个小时 $n=4$ 的情况，终于试出来：

if(n==4)
{
	cout<<0<<endl;
	cout<<"0 1 2 3\n1 0 3 2\n2 3 0 1\n3 2 1 0\n0 0 0 0\n0 1 2 3\n0 2 3 1\n0 3 1 2"<<endl;
	return 0;
}

然后没有思绪。

于是在网上找"有限域"，发现需要：

相加或相乘再模 $p$ ，就是 $p$ 进制中个位的运算。那么 $n=p^k$ 的情况也就能解决了。

这里，每个有限域中的数都是一个多项式的值的 $p$ 进制的一个数位。于是解决了加法。

找出一个系数在 $[0,p)$ 中的 $k$ 次既约多项式，这里 $k\leqslant 8$ .关键是想要如何找到。

再把它与原多项式相乘再模 $p$ 处理即可，正确性显然。

$p=2$ 时，加法只需要把两个数异或一下。乘法怎么办？

举 $3\times 5$ 的例子：

$3=(11)_2=p+1(p=2)$

$5=(101)_2=p^2+1(p=2)$

$3\times 5=(p+1)(p^2+1)=p^3+p^2+p+1$

但这个数已经大于 $8$ 了，于是我们模一个不可约多项式 $p^3+p+1$ ，得到 $p^2$ ，于是 $3\times 5=4$ .

当然多项式也不好找，需要自己动脑筋。

下附所有 $2$ 的幂情况标程：

#include<bits/stdc++.h>
using namespace std;
#define N 17
int p;
struct f//多项式
{
	int a[N];
	int dr()
	{
		for(int i=N-1;i>=0;i--)
			if(a[i]!=0)	return i;
		return 0;	
	}
	inline void clr()
	{
		for(int i=0;i<N;i++)	a[i]=0;
		return;
	}
	inline void mod()
	{
		for(int i=0;i<N;i++)	a[i]%=p;
		return;
	}
};
inline f mul(f x,int l)//数乘
{
	for(int i=0;i<N;i++)	x.a[i]*=l;
	return x;
}
f gt(int x)//数转换为多项式
{
	f ans;ans.clr();
	for(int i=0;;i++)
	{
		if(x==0)	return ans;
		else{ans.a[i]=x%p;x/=p;}
	}
}
int ungt(f ans)//多项式转为数
{
	int x=0;
	for(int i=ans.dr();i>=0;i--)
		x=(x*p)+ans.a[i];
	return x; 
}
f add(f x,f y)//加
{
	for(int i=0;i<=N;i++)
		x.a[i]=(x.a[i]+y.a[i])%p;
	return x;
}
f yiw(f x,int sum)//移位
{
	for(int i=x.dr();i>=0;i--)	x.a[i+sum]=x.a[i];
	for(int i=sum-1;i>=0;i--)	x.a[i]=0;
	return x;
}
f prod(f x,f y)//多项式相乘
{
	f ans;ans.clr();
	for(int i=0;i<=x.dr();i++)
	{
		if(x.a[i]!=0)	ans=add(ans,mul(yiw(y,i),x.a[i]));
	}
	ans.mod();
	return ans;
}
f Mod(f x,f y)//多项式取模
{
	int sg=y.dr()-1;
	for(int i=x.dr();i>=sg+1;i--)
	{
		if(x.a[i]==0)	continue;
		else
		{
			x=add(x,mul(yiw(y,i-sg-1),p-x.a[i]));
			x.mod();
		}
	}
	return x;
}
f Num(int x)//找多项式
{
	f ans;ans.clr();
	if (x==8)ans.a[0]=ans.a[1]=ans.a[3]=1;
	if (x==256)	ans.a[8]=ans.a[4]=ans.a[3]=ans.a[1]=ans.a[0]=1;
	if (x==16)	ans.a[2]=ans.a[4]=ans.a[3]=ans.a[1]=ans.a[0]=1;
	if (x==128)	ans.a[7]=ans.a[6]=ans.a[5]=ans.a[2]=ans.a[0]=1;
	return ans;
}

主函数内的：

	case 256:case 128:case 8:
        {
        	p=2;
            cout<<0<<endl;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cout<<(i^j);
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
            }
            for(int i=0;i<n;i++)
            {
            	for(int j=0;j<n;j++)
                {
                    f x=gt(i);
                    f y=gt(j);
                    f z=prod(x,y);
                    z=Mod(z,Num(n));
                    int ans=ungt(z);
                    cout<<ans;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
			}
        }break;

最后，给出满分程序，但是多项式请自己找。

#include<bits/stdc++.h>
using namespace std;
#define N 17
int p;
struct f
{
	int a[N];
	int dr()
	{
		for(int i=N-1;i>=0;i--)
			if(a[i]!=0)	return i;
		return 0;	
	}
	inline void clr()
	{
		for(int i=0;i<N;i++)	a[i]=0;
		return;
	}
	inline void mod()
	{
		for(int i=0;i<N;i++)	a[i]%=p;
		return;
	}
};
inline f mul(f x,int l)
{
	for(int i=0;i<N;i++)	x.a[i]*=l;
	return x;
}
f gt(int x)
{
	f ans;ans.clr();
	for(int i=0;;i++)
	{
		if(x==0)	return ans;
		else{ans.a[i]=x%p;x/=p;}
	}
}
int ungt(f ans)
{
	int x=0;
	for(int i=ans.dr();i>=0;i--)
		x=(x*p)+ans.a[i];
	return x; 
}
f add(f x,f y)
{
	for(int i=0;i<=N;i++)
		x.a[i]=(x.a[i]+y.a[i])%p;
	return x;
}
f yiw(f x,int sum)
{
	for(int i=x.dr();i>=0;i--)	x.a[i+sum]=x.a[i];
	for(int i=sum-1;i>=0;i--)	x.a[i]=0;
	return x;
}
f prod(f x,f y)
{
	f ans;ans.clr();
	for(int i=0;i<=x.dr();i++)
	{
		if(x.a[i]!=0)	ans=add(ans,mul(yiw(y,i),x.a[i]));
	}
	ans.mod();
	return ans;
}
f Mod(f x,f y)
{
	int sg=y.dr()-1;
	for(int i=x.dr();i>=sg+1;i--)
	{
		if(x.a[i]==0)	continue;
		else
		{
			x=add(x,mul(yiw(y,i-sg-1),p-x.a[i]));
			x.mod();
		}
	}
	return x;
}
f Num(int x)
{
	//自己找
}
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    if(n==4){cout<<0<<endl;cout<<"0 1 2 3\n1 0 3 2\n2 3 0 1\n3 2 1 0\n0 0 0 0\n0 1 2 3\n0 2 3 1\n0 3 1 2"<<endl;return 0;}
    switch(n)
    {
        case 6:case 143:cout<<"-1";break;
        case 3:case 19:case 89:case 181:case 233:
        {
            cout<<"0"<<endl;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cout<<(i+j)%n;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
            }
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cout<<(i*j)%n;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
            }
        }break;
        case 256:case 128:case 8:
        {
        	p=2;
            cout<<0<<endl;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cout<<(i^j);
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
            }
            for(int i=0;i<n;i++)
            {
            	for(int j=0;j<n;j++)
                {
                    f x=gt(i);
                    f y=gt(j);
                    f z=prod(x,y);
                    z=Mod(z,Num(n));
                    int ans=ungt(z);
                    cout<<ans;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
			}
        }break;
        default:
        {
        	p=...//自己写if
        	cout<<0<<endl;
        	for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    f x=gt(i);
                    f y=gt(j);
                    f z=add(x,y);
                    int ans=ungt(z);
                    cout<<ans;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
            }
            for(int i=0;i<n;i++)
            {
            	for(int j=0;j<n;j++)
                {
                    f x=gt(i);
                    f y=gt(j);
                    f z=prod(x,y);
                    z=Mod(z,Num(n));
                    int ans=ungt(z);
                    cout<<ans;
                    if(j==n-1)continue;
                    else cout<<' ';
                }
                cout<<endl;
			}
		}
    }
    return 0;
}

P.S.

这里简略地证明一下有限域的元素个数必为 $p^n$ 的形式，其中 $p$ 为素数，下文中字母 $p$ 未加说明均为素数。我们假定读者学过群论。

"环"的定义详见此。

环同态基本定理与群同态基本定理很类似。学过群论的应该都知道群同态基本定理，所以笔者认为不必介绍环的像、 $\text{kernel}$ (核)、环同态和环同态基本定理。

设有限域为 $GF(k),k$ 为有限域元素个数。显然存在 $GF(p)$ .

定义1.设 $F$ 是域。使得 $n·1=0$ 的最小正整数 $n$ 称为 $F$ 的特征。若不存在这样的正整数称其特征为 $0$ 。我们把特征记为 $char(F)$ .

引理1. 设 $F$ 为一个域，若 $char(F)>0$ ，则 $char(F)$ 必为素数。

证明：反证法，设 $n=char(F)$ ，若 $n$ 为合数，则 $n=uv$ ， $u>1,v>1$ 为整数。故 $(u·1)(v·1)=(uv)·1=n·1=0$ . 由 $n$ 的最小性知 $u·1≠0$ ，从而 $u·1$ 有逆元 $(u·1)^{-1}$ 。上式两端同乘 $(u·1)^{-1}$ 知 $v·1=0$ ，与 $n$ 的最小性矛盾！

引理2. 设 $F$ 为域。若 $char(F)=p>0$ ，则 $F$ 必有与 $GF(p)$ 同构的子域。

证明：定义映射

\varphi: \mathbb{Z} \rightarrow F

n \mapsto n·1

显然 $\varphi$ 是环同态。我们断言 $\ker \varphi=p\mathbb{Z}.$ 设 $n∈\ker \varphi,$ 即 $n·1=0∈F.$ 设 $n=qp+r\ (q,r∈\mathbb{Z}, 0\leqslant r<q)$ 则有 $0=n·1=q(p·1)+r·1=r·1$ ，由 $char$ 的定义知 $p$ 只能为 $0$ . 故 $n∈p\mathbb{Z}$ ，这说明 $\ker \varphi \subseteq p\mathbb{Z}.$

反之，对 $n∈p\mathbb{Z}$ 设 $n=pq$ ，则 $\varphi(n)=(qp)·1=q(p·1)=0$ ，从而 $n∈\ker \varphi$ ，即 $p\mathbb{Z}\subseteq\ker \varphi.$

故断言成立。由环同态基本定理， $GF(p)=\mathbb{Z}/p\mathbb{Z}\cong \text{im}\ \varphi $.

由 $\text{im}\ \varphi$ 为 $F$ 的子域，故证毕。

回到原问题，设 $K$ 为有限域，则 $K$ 包含 $GF(p)$ ，且 $K/GF(p)$ 必为有限扩张（定义见此），故 $|K|$ 只有一个素因子，证毕！

P.S.P.S. 题外话：可以证明所有的 $GF(p^n)$ 均同构，所以上面的构造相当于是唯一的。

ID

2882

时间

1000~3000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

大学数学题

信息

1 条题解

自动搬运

以下是正文

大学数学题

信息

还没有账户？

登录