题目

传送门 to luogu

思路

我好弱 ????

一、判断无解

$n=1$ 一律不考虑，因为答案就是单个 $1$ 就完了。

首先 $n$ 一定在末尾，因为一旦含有 $n$ ，模 $n$ 就肯定是 $0$ 了。那么倒数第二个前缀积就是 $(n-1)!$ ，这个值就不能为 $0$ 。什么情况下 $(n-1)!$ 是 $n$ 的倍数呢？

1.单个质因数

假设 $n=p^q$ ，其中 $p$ 是一个质数。那么 $(n-1)!$ 中含有的 $p$ 的指数为

$$\sum _{i=1}^{+\infty }\lfloor \frac{p^q-1}{p^i}\rfloor$$

显然 $i=1$ 这一项的贡献就已经是 $\lfloor p^{q-1}-\frac{1}{p}\rfloor =p^{q-1}-1$ 了。这玩意儿可能小于 $q$ 吗？

显然指数型函数增长的更快。所以 $q$ 越大，越不可能实现这一目的。我们不妨手推较小的几个 $q$ 。

• 当 $q=1$ 时，$n$ 就是一个素数，显然 $(n-1)!\equiv n-1\ne 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$ 。
• 当 $q=2$ 时，原不等式等价于 $p-1<2$ ，可知 $p=2$ 。代入知 $2^2=4$ 是一个特殊解，因为 $3!=6$ 不是 $4$ 的倍数。
• 当 $q=3$ 时，$p^2-1<3$ ，已经无法做到了。容易判断，$q>3$ 亦无解。

综上：$n$ 的质因数只有一个的时候，$n$ 不为素数且 $n\ne 4$ 则 $(n-1)!$ 是 $n$ 的倍数。

2.多个质因数

不妨设 $n=p_1^{q_1}{p}_2^{q_2}\cdots p_k^{q_k}$ ，其中 $p_i$ 为质数，$q_i$ 均不为零。

显然任何一个质因数都是真因子，即 $p_i^{q_i}<n$ ，所以 $(n-1)!$ 中包含了每一个 $p_i^{q_i}$ 。于是 $(n-1)!$ 是 $n$ 的倍数。

3.综上可得

$n$ 必须为素数，或者 $n=4$ 才可能有解。

二、生成一组解

对于 $n=4$ 的情况，$⟨1,3,2,4⟩$ 是可以自己手玩出的解。

$n$ 是素数怎么办？我在这里卡了 $2h$ 无果。其实主要是因为我太弱。

答案是 $⟨1,\frac{2}{1},\frac{3}{2},\dots ,\frac{n-1}{n-2},n⟩$ 即可。这里的分数可以用逆元转化为一个整数。

显然这里的数字是两两不同的，因为 $\frac{x}{x-1}=1+\frac{1}{x-1}$ ，如果某两个数字相同，就说明其逆元相等。这可太离谱了。而且这个值也不可能是 $1$ 。

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x%10)^48);
}
inline int qkpow(int_ b,int q,int m){
	int ans = 1;
	for(; q; q>>=1,b=b*b%m)
		if(q&1) ans = ans*b%m;
	return ans;
}

const int MaxN = 100005;
int inv[MaxN], ans[MaxN];

int main(){
	int n = readint();
	if(n == 4){
		puts("YESn1n3n2n4");
		return 0;
	}
	for(int i=2; 1ll*i*i<=n; ++i)
		if(n%i == 0){
			puts("NO"); return 0;
		}
	puts("YES");
	inv[1] = 1;
	for(int i=2; i<n; ++i)
		inv[i] = (0ll+n-n/i)*inv[n%i]%n;
	ans[1] = 1;
	for(int i=2; i<n; ++i)
		ans[i] = 1ll*i*inv[i-1]%n;
	for(int i=1; i<n; ++i)
		printf("%dn",ans[i]);
	printf("%dn",n);	
	return 0;
}

最后

以上就是专一康乃馨为你收集整理的[CF487C]Prefix Product Sequence题目思路代码的全部内容，希望文章能够帮你解决[CF487C]Prefix Product Sequence题目思路代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。