P3599 Koishi Loves Construction

P3599 Koishi Loves Construction 对于 Task 1，首先 nn 肯定要放在第一个，否则会出现两个前缀和模 nn 相等。 其次考虑 nn 为奇数的情况显然是不成立的，因为总和为 n(n+1)2\frac{n(n+1)}{2}，显然模 nn 为 0，同样会出现两个前缀和模 nn 相等。 考虑打表，发现一种构造形式，正确性读者自证不难，两两结合着看即可： n, n−1, 2, n−3, 4, ..., 1n,\ n-1,\ 2,\ n-3,\ 4,\ ...,\ 1 对于 Task 2，考虑 1 要放在第一个，nn 要放在最后一个，可以构造一个分数序列： 1,21,32,...,n1,\frac{2}{1},\frac{3}{2},...,n 不难证明求逆元后的余数与 [0,n)[0,n) 中的数一一对应，所以就做完了。 代码： #include using namespace std; #define int long long const int N=1e5+5; int x,T; int n,idx; int vis[N],prm[N],isprm[N]; void prime(){ for(int i=2;i>=1; } return res; } signed main(){ prime(); cin>>x>>T; while(T--){ cin>>n; if(x==1){ if(n==1){ cout `#include using namespace std; #define int long long const int N=1e5+5; int x,T; int n,idx; int vis[N],prm[N],isprm[N]; void prime(){ for(int i=2;i if(!vis[i]) prm[++idx]=i,isprm[i]=1; for(int j=1;1ll*i*prm[j] vis[i*prm[j]]=1; if(i%prm[j]==0) break; } } } int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=n; (x*=x)%=n,y>>=1; } return res; } signed main(){ prime(); cin>>x>>T; while(T--){ cin>>n; if(x==1){ if(n==1){ cout"2 1\n"; continue; } else if(n&1){ cout"0\n"; continue; } cout"2 "" "; int cnt1=n-1,cnt2=2; for(int i=2;i2){ cout" "" "; cnt1-=2,cnt2+=2; } cout"1\n"; } if(x==2){ if(n==1){ cout"2 1\n"; continue; } if(n==4){ cout"2 1 3 2 4\n"; continue; } if(!isprm[n]){ cout"0\n"; continue; } cout"2 1 "; for(int i=1;i2;i++) cout1+qpow(i,n-2))%n" "; cout"\n"; } } return 0; }`