点此看题
解法一
首先我们来判断一下有无解，如果 n ≤ 4 n\leq 4 n≤4或者 n n n是质数的话就有解，否则无解。因为我们可以找到 a , b a,b a,b使得 n ∣ a b n|ab n∣ab成立， a , b a,b a,b可以用如下方法取得：
如果 n n n不是一个质数的完全平方数，那么一定存在 a b = n ab=n ab=n（把 n n n的因子分出去）否则 p 2 = n p^2=n p2=n，那么我们取 p p p和 2 p 2p 2p就行了（这里 p > 2 p>2 p>2）因为是要构造出 [ 1 , n ] [1,n] [1,n]的所有数，所以可以利用原根，首位可以确定是 1 1 1，末尾可以确定是 n n n，然后用如下方法构造（注意 g n − 1 = 1 g^{n-1}=1 gn−1=1）： g 0 , g n − 2 , g 2 , g n − 4 . . . . . . . n g^0,g^{n-2},g^2,g^{n-4}.......n g0,gn−2,g2,gn−4.......n那么前缀积就是： g 0 , g n − 2 , g 1 , g n − 3 . . . . . . . n g^0,g^{n-2},g^1,g^{n-3}.......n g0,gn−2,g1,gn−3.......n如何求原根，先找到 φ \varphi φ的所有质因数，枚举可能的原根，用这些质因数去验证，不能存在： g φ y s [ i ] = 1 m o d n g^{\frac{\varphi}{ys[i]}}=1\mod n gys[i]φ=1modn因为不能提前出现数的循环（数两两不同），而 1 1 1就是出现循环的标志。
解法二
看能不能构造 1 , 2... n 1,2...n 1,2...n的前缀积，首项是 1 1 1，末项是 n n n，看 x x x和 x + 1 x+1 x+1： x a [ x + 1 ] = x + 1 m o d n xa[x+1]=x+1\mod n xa[x+1]=x+1modn x ( a [ x + 1 ] − 1 ) = 1 m o d n x(a[x+1]-1)=1\mod n x(a[x+1]−1)=1modn逆元是一一对应的，构造成立，下面给出解法一的代码。
#include <cstdio> const int M = 100005; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,cnt,vis[M],p[M],g[M]; void sieve(int n) { for(int i=2;i<=n;i++) { if(!vis[i]) p[++cnt]=i; for(int j=1;j<=cnt && i*p[j]<=n;j++) { vis[i*p[j]]=1; if(i%p[j]==0) break; } } } int qkpow(int a,int b) { int r=1; while(b>0) { if(b&1) r=r*a%n; a=a*a%n; b>>=1; } return r; } signed main() { n=read(); if(n==1) {puts("YES\n1");return 0;} if(n==2) {puts("YES\n1\n2");return 0;} if(n==3) {puts("YES\n1\n2\n3");return 0;} if(n==4) {puts("YES\n1\n3\n2\n4");return 0;} sieve(n); if(vis[n]) {puts("NO");return 0;} int phi=n-1,G=0; for(int i=1;i<=cnt;i++) if(phi%p[i]==0) g[++m]=p[i]; for(int i=2;i<n;i++) { bool fuck=1; for(int j=1;j<=m;j++) if(qkpow(i,phi/g[j])==1) fuck=0; if(fuck) G=i; } puts("YES"); for(int i=0;i<(n-1)/2;i++) printf("%lld\n%lld\n",qkpow(G,2*i),qkpow(G,n-2*(i+1))); printf("%lld\n",n); }