文章目录

一.题目二.Solution三.CodeThanks！

一.题目

题目描述 是否存在一个长度为$n$的排列，使得其前缀积在$modn$意义下两两不同？ 输入 一行一个正整数$n(1\le n\le 10^5)$ 输出 如果存在，输出一行$YES$，接下来$n$行每行一个数表示这个排列；如果不存在，输出一行$NO$ 传送门

二.Solution

这道题目很巧妙。 首先考虑一些题目给你的特定条件。 很明显，第一个数必须是1，最后一个数必须是n，如果1在中间，那么就会出现余数相同的情况，如果n在中间，那么n之后的前缀积都能被n整除。然后所有大于4的合数都没有解，4有解是因为4=2*2，可以构造出解：1,3,2,4。 其次，我们来想一种构造的方法： 这样构造： $$1,\frac{2}{1},\frac{3}{2},\frac{4}{3},...,\frac{n}{n-1}$$ 那么它的前缀积就是： $$1,2,3,4,...,n$$ 涵盖了所有余数并且还没有重复，我们将构造的数的除法变成$modn$意义下的逆元，$n$是质数，就构造出解了： $$1,2\ast 1^{-1},3\ast 2^{-1},4\ast 3^{-1},...,n\ast (n-1{)}^{-1}$$ 这种奇妙的方法要贴近题目来看才能发现，所以数学题目一般答案都在题目当中。

三.Code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define M 100005 #define LL long long int n; LL ans[M]; bool vis[M]; bool check (int x){ for (int i = 2; i < x; i ++){ if (x % i == 0) return 0; } return 1; } LL qkpow (LL x, LL y, LL mod){ LL res = 1; while (y){ if (y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } int main (){ scanf ("%d", &n); if (n == 4){ printf ("YES\n1\n3\n2\n4\n"); return 0; } if (! check (n)){ printf ("NO\n"); return 0; } ans[1] = 1, ans[n] = n; for (int i = 2; i < n; i ++){ ans[i] = 1ll * i * qkpow (i - 1, n - 2, n) % n; } printf ("YES\n"); for (int i = 1; i <= n; i ++) printf ("%lld\n", ans[i]); return 0; }

Thanks！