题解 P3923 【大学数学题】

Drystynt · 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 处理即可，正确性显然。

但这个数已经大于 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 是环同态。我们断言 \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.

故断言成立。由环同态基本定理，