自动搬运

查看原文

来自洛谷，原作者为

	a326820068122c RP++

搬运于2025-08-24 22:15:37，当前版本为作者最后更新于2022-07-29 15:59:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题首先不难想到需要每个置换能形成环才能满足 $p(p(...(p(i))...))=i$ 成立。

然后 order 是所有环大小的 LCM。

令环的大小为 $x_1x_2...x_k$ （这里为了方便令$x_1 \le x_2 \le ... \le x_k$）其实就是把寻找最大的 $lcm(x_1,x_2,...,x_k)$ 使得 $x_1+x_2+...+x_k=n$。

对于先考虑如何让一个固定的 $x_1,x_2,...,x_k$ 使得字典序最小。

由于是字典序，可以考虑贪心，首先对于一组数 $y_1y_2...y_t$ 满足 $y_1 \le y_2 \le ... \le y_t$）形成的环最小是 $y_2,y_3,...,y_t,y_1$,那么对于多个环，每次应该可以会到$y_1$时就回到$y_1$（可以理解成拿最小的一个环进行贪心）。

很显然，一定存在一个最优解使所有 $x$ 互质（假设$\gcd(x_a,x_b)>1$,则必然存在质因数 $p$ 使$p|x_a$且$p|x_b$,不妨令 $x_b$质因数分解中 $p$的指数更大, 则$x_a,x_b$ 可以改成 $x_a/p,x_b,1,1,1...(x_a-x_a/p$ 个 $1$) 使和、LCM 不变，字典序会更优。

然后发现如果一个数 $x$ 含有超过 $2$ 个质因子它一定不优秀,设他的其中两个质因子为 $p,q$ 其必然能写成 $x=p^a*q^b*c$ 其中能保证 $p^a,q^b*c$ 两部分都 $\ge2$ 所以 $p^a*q^b*c\ge p^a+q^b*c$ （若 $a,b\ge2$ 则 $(a-1)(b-1)\ge1$，则$ab\ge a+b$），则 $x$ 可以改成 $p^a,q^b*c$ 使和不变，LCM 不变差，字典序会更优。

综上，$x_1,x_2,...,x_k$ 为 $1$ 或不同质数次方。

于是可以先筛出 $[2,10000]$ 所有的质数，

然后进行带路径记录的分组背包（可以理解成对于每个质数 $p$ 在 $0,1$、$p,p$、$p^2,p^2...$ 中选一个(当然贡献是相乘的，不是平常背包里的相加）。

这里有两个小细节 :

一，可以采用 long double 来代替高精度，由于只需比较大小，不需输出，所以不需要那么高的精度（实测可以过）。

二，不难发现比较大的质数并不会被选中，我们可以先让程序用 $[2,10000]$ 所有的质数进行 dp，然后再循环出 $[1,10000]$ 所有数中最大可能用到的最大质数 $p_{\max}$，然后再用 $[2,p_{\max}]$ 所有的质数进行 dp 。

最后放一下代码：

#include <bits/stdc++.h>
#define for1(i,n) for(i=1;i<=(n);i++)
#define forlr(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
typedef long double ld;
const int N=10005,D=10000;
int z[N],cz,n,pre[75][N],T,c[N],cc;
bool b[N];
ld dp[75][N];
int main(){
	int i,j,k;
	forlr(i,2,D){
		if(!b[i]) z[++cz]=i;
		if(cz==72) break;
		for(j=1;z[j]*i<=D;j++){
			b[z[j]*i]=1;
			if(!(i%z[j])) break;
		}
	}
	forlr(i,0,D) dp[0][i]=1;
	for1(j,cz){
		forlr(i,0,D) pre[j][i]=0,dp[j][i]=dp[j-1][i];
		forlr(i,0,D) for(k=z[j];i+k<=D;k*=z[j]) if(dp[j][i+k]<dp[j-1][i]*k)
			pre[j][i+k]=k,dp[j][i+k]=dp[j-1][i]*k;
	}
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);cc=0;
		for(i=cz;i;i--) if(pre[i][n]) n-=(c[++cc]=pre[i][n]);
		sort(c+1,c+cc+1);
		for1(i,n) printf("%d ",i);
		for1(j,cc){
			forlr(k,i,i+c[j]-2) printf("%d ",k+1); 
			printf("%d ",i);i+=c[j];
		}
		puts("");
	}
	return 0;
}