Prefix Product Sequence CodeForces - 487C (数论,构造)

大意: 构造一个[1,2,...n]的排列, 使得前缀积模n为[0,1,...,n-1]的排列

 

这种构造都好巧妙啊, 大概翻一下官方题解好了

对于所有>=6的合数$n$, 有$(n-1)! equiv 0 space (mod space n)$, 一定不成立

对于素数可以构造$[1,frac{2}{1},frac{3}{2},frac{4}{3},...,frac{n-1}{n-2},n]$, 或者构造$[1,g,g^{-2},g^3,g^{-4},...,n]$, $g$为$n$的原根

#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;

const int N = 1e6+10;
int n, inv[N];

int check(int x) {
	int mx = sqrt(x+0.5);
	REP(i,2,mx) if (x%i==0) return 0;
	return 1;
}

int main() {
	scanf("%d", &n);
	if (n==1) return puts("YESn1"),0;
	if (n==4) return puts("YESn1n3n2n4"),0;
	if (!check(n)) return puts("NO"),0;
	puts("YESn1");
	inv[1] = 1;
	REP(i,2,n-1) { 
		inv[i] = (ll)inv[n%i]*(n-n/i)%n;
		printf("%dn", int((ll)i*inv[i-1]%n));
	}
	printf("%dn", n);
}