题解 P3599 【Koishi Loves Construction】

2020-06-05 23:10:38


Task 1: $> 1$ 的奇数无解,$1$ 的解显然

偶数的一种可行解为 $0,1,-2,3,-4,\cdots,n-1$ 把 $\leq 0$ 的数 $+n$ 即可

Task 2: 我想不出来官方题解那么妙的构造怎么办?

可以转化为Task1解决。

$>4$ 的合数无解,$1,2,4$ 的解显然

对于奇质数的情况根据某定理恰有 $\varphi(n-1)$ 个原根,(通过随机+暴力判定可以较高效地)任取一个原根,设其为 $g$

将 $g^0,g^1,\cdots,g^{n-2}$ 一一映射到 $0,1,\cdots,n-2$ 即可转化为 $n'=n-1$ 版本的Task1(显然 $n-1$ 是偶数)

在以上结果的结尾添加一个 $n$ 就是Task2的一种构造

代码

#include<bits/stdc++.h>
using namespace std;
int ty,T,n;
std::mt19937 ran;
int pw[111111],fl[111111];//pw存原根的幂
bool ok(int g)//暴力检验是否为原根
{
    memset(fl,0,sizeof(fl));
    pw[0]=1;fl[1]=1;
    for(int i=1;i<n-1;i++)
    {
        pw[i]=1ll*pw[i-1]*g%n;
        if(fl[pw[i]])return false;
        fl[pw[i]]=1;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    ran.seed(0);
    cin>>ty>>T;
    while(T--)
    {
        cin>>n;
        if(ty==1)
        {
            if(n==1)cout<<"2 1"<<endl;
            else if(n%2==0)
            {
                cout<<2<<' '<<n;
                for(int i=1;i<n;i++)cout<<' '<<(i%2?i:n-i);
                cout<<endl;
            }
            else cout<<0<<endl;
        }
        else
        {
            if(n==1)cout<<"2 1"<<endl;
            else if(n==2)cout<<"2 1 2"<<endl;
            else if(n==4)cout<<"2 1 3 2 4"<<endl;
            else
            {
                int zz=1;//是否质数
                for(int i=2;i*i<=n;i++)
                {
                    if(n%i==0)
                    {
                        zz=0;
                        break;
                    }
                }
                if(!zz)cout<<0<<endl;
                else
                {
                    int g=ran()%(n-1)+1;
                    while(!ok(g))g=ran()%(n-1)+1;
                    cout<<2<<' '<<pw[0];
                    for(int i=1;i<n-1;i++)cout<<' '<<(i%2?pw[i]:pw[n-1-i]);
                    cout<<' '<<n<<endl;
                }
            }
        }
    }
    return 0;
}