J.Permutation and Primes

J.Permutation and Primes

题意

给定一个正整数 $nn$ ，构造一个 $nn$ 的排列，使得每对相邻元素的和或差的绝对值为一奇素数

题解

逛了一圈过了的代码，好像没看到我这个做法。

$nn$ 比较小就打表。

$nn$ 如果是偶数，则存在 $p_1+p_2=np\_1+p\_2=n$，$p_1,p_{2}p\_1,p\_2$ 是质数，构造 $a[i]=((i{p}_1-1)\mathrm{m}\mathrm{o}\mathrm{d}n)+1a[i]=((ip\_1-1)\backslash bmod\; n)+1$ 即可。

$nn$ 如果是奇数，则 $n+1n\; +1$ 到 $n\times 2+1n\backslash times2+1$ 之间有一个质数 $p_{3}p\_3$，找 $p_1+p_2=n-1p\_1+p\_2=n-1$，然后构造 $a[1]=n,a[2]=p_3-n,a[i]=(a[2]+(i-2)p_1-1\mathrm{m}\mathrm{o}\mathrm{d}(n-1))+1a[1]=n,a[2]=p\_3-n,a[i]=(a[2]+(i-2)p\_1-1\; \backslash bmod\; (n-1))+1$。