题解 P3599 【Koishi Loves Construction】
oscar
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的一种构造
代码
```cpp
#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;
}
```