CF487C Prefix Product Sequence 题解

题目大意

题目传送门
给你一个正整数 $n$，请你构造一个长度为 $n$ 的只包含 $1\sim n$ 排列，使得前缀积在 $n$ 意义下两两不同。

题目分析

首先，我们可以确定：第一位一定是 $1$ （这个显然），最后一位一定是 $n$，我们可以采用反证法：
设 $n$ 填在第 $x$ （ $2\le x<n$ ）位，则 $1\sim x$ 位的积 $\mathrm{mod}n$ 一定是 $0$，而第 $x+1$ 位的前缀积 $\mathrm{mod}n$ 也是 $0$，不符合题意，则 $n$ 只能填在最后一位。
接下来我们考虑 $n$，如果它是一个合数，则无解( $4$ 除外)
因为 $n$ 是一个合数，则它一定能分解成 $a\times b$。我们设他们分别在第 $x$ 和第 $y$ 位。不妨设 $x<y$，则第 $y$ 位的前缀积 $\mathrm{mod}n$ 一定位 $0$ （因为 $a\times b=n$ ），而第 $n$ 位的前缀积也为 $0$，不符合题意。
所以我们得出了结论：当 $n$ 为合数（除了 $4$ ），无解。
接下来我们考虑素数怎么构造。
因为我们知道第 $1$ 位的前缀积一定是 $1$，第 $n$ 位的前缀和 $\mathrm{mod}n$ 的值为 $0$ ，所以我们就考虑将前缀和构造成 $1,2,3,4\cdots n-1,0$ 的形式。
如果这样，我们将 $a$ 构造成 $1,\frac{2}{1},\frac{3}{2}\cdots \frac{n-1}{n-2},n$ 即可，而除号可以理解成逆元。
最后别忘记特判 $1$ 和 $4$ 的情况即可。

CODE

#include
using namespace std;
#define R register
#define ri register int
#define int long long
#define ull unsigned long long
#define lid (id<<1)
#define rid (id<<1|1)
void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
const int N=2001;
inline int read();
inline void write(int ans);
inline void put(int x,char c);
int n;
bool prime(int x){
	if(x<2)return 0;
	if(x==2)return 1;
	if(x%2==0)return 0;
	for(int i=3;i*i<=x;i+=2){
		if(x%i==0)return 0;
	}
	return 1;
}
int qow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%n;
		b>>=1,a=a*a%n;
	}
	return ans;
}
signed main(){
//	ios_base::sync_with_stdio(0);
	n=read();
	if(n==1){
		cout<<"YES\n1";
		return 0;
	}
	if(n==4){
		puts("YES\n1\n3\n2\n4");
		return 0;
	}
	if(!prime(n)){
		cout<<"NO\n";
		return 0;
	}//1 2/1 3/2 4/3
	printf("YES\n1\n");
	for(int i=2;i<=n;i++){
		int x=i*qow(i-1,n-2)%n;
		if(x==0)x=n;
		printf("%lld\n",x);
	}
	return 0;
}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x;}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x % 10+'0');return;}
inline void put(int x,char c){write(x);putchar(c);return;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

有不理解的地方可以私信找我