传送门 to luogu
我好弱 😢
n = 1 n=1 n=1 一律不考虑，因为答案就是单个 1 1 1 就完了。
首先 n n n 一定在末尾，因为一旦含有 n n n ，模 n n n 就肯定是 0 0 0 了。那么倒数第二个前缀积就是 ( n − 1 ) ! (n-1)! (n−1)! ，这个值就不能为 0 0 0 。什么情况下 ( n − 1 ) ! (n-1)! (n−1)! 是 n n n 的倍数呢？
假设 n = p q n=p^q n=pq ，其中 p p p 是一个质数。那么 ( n − 1 ) ! (n-1)! (n−1)! 中含有的 p p p 的指数为
∑ i = 1 + ∞ ⌊ p q − 1 p i ⌋ \sum_{i=1}^{+\infty}\left\lfloor\frac{p^q-1}{p^i}\right\rfloor i=1∑+∞⌊pipq−1⌋
显然 i = 1 i=1 i=1 这一项的贡献就已经是 ⌊ p q − 1 − 1 p ⌋ = p q − 1 − 1 \lfloor p^{q-1}-\frac{1}{p}\rfloor=p^{q-1}-1 ⌊pq−1−p1⌋=pq−1−1 了。这玩意儿可能小于 q q q 吗？
显然指数型函数增长的更快。所以 q q q 越大，越不可能实现这一目的。我们不妨手推较小的几个 q q q 。
当 q = 1 q=1 q=1 时， n n n 就是一个素数，显然 ( n − 1 ) ! ≡ n − 1 ≠ 0 ( m o d n ) (n-1)!\equiv n-1\ne 0\pmod{n} (n−1)!≡n−1=0(modn) 。当 q = 2 q=2 q=2 时，原不等式等价于 p − 1 < 2 p-1<2 p−1<2 ，可知 p = 2 p=2 p=2 。代入知 2 2 = 4 2^2=4 22=4 是一个特殊解，因为 3 ! = 6 3!=6 3!=6 不是 4 4 4 的倍数。当 q = 3 q=3 q=3 时， p 2 − 1 < 3 p^2-1<3 p2−1<3 ，已经无法做到了。容易判断， q > 3 q>3 q>3 亦无解。综上： n n n 的质因数只有一个的时候， n n n 不为素数且 n ≠ 4 n\ne 4 n=4 则 ( n − 1 ) ! (n-1)! (n−1)! 是 n n n 的倍数。
不妨设 n = p 1 q 1 p 2 q 2 ⋯ p k q k n=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k} n=p1q1p2q2⋯pkqk ，其中 p i p_i pi 为质数， q i q_i qi 均不为零。
显然任何一个质因数都是真因子，即 p i q i < n p_i^{q_i}<n piqi<n ，所以 ( n − 1 ) ! (n-1)! (n−1)! 中包含了每一个 p i q i p_i^{q_i} piqi 。于是 ( n − 1 ) ! (n-1)! (n−1)! 是 n n n 的倍数。
n n n 必须为素数，或者 n = 4 n=4 n=4 才可能有解。
对于 n = 4 n=4 n=4 的情况， ⟨ 1 , 3 , 2 , 4 ⟩ \langle 1,3,2,4\rangle ⟨1,3,2,4⟩ 是可以自己手玩出的解。
n n n 是素数怎么办？我在这里卡了 2 h 2h 2h 无果。其实主要是因为我太弱。
答案是 ⟨ 1 , 2 1 , 3 2 , … , n − 1 n − 2 , n ⟩ \left\langle 1,\frac{2}{1},\frac{3}{2},\dots,\frac{n-1}{n-2},n\right\rangle ⟨1,12,23,…,n−2n−1,n⟩ 即可。这里的分数可以用逆元转化为一个整数。
显然这里的数字是两两不同的，因为 x x − 1 = 1 + 1 x − 1 \frac{x}{x-1}=1+\frac{1}{x-1} x−1x=1+x−11 ，如果某两个数字相同，就说明其逆元相等。这可太离谱了。而且这个值也不可能是 1 1 1 。
