pku3590 The shuffle Problem

将n分解为几部分，使得这几部分的最小公倍数最大，显然分解开的各部分应该有p^k的形式，其中p是素数
因为n最大为100，所以直接枚举即可，不过别人有说只用前9个素数就行，我不知道怎么证明

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;

const int maxn = 105;
bool isp[maxn];
int p[maxn], lp;
void make()
{
	memset(isp, true, sizeof(isp));
	lp = 0;
	for (int i = 2; i < maxn; ++i)
		if (isp[i])
		{
			p[lp++] = i;
			for (int j = i * i; j < maxn; j += i)
				isp[j] = false;
		}
}
int step[maxn], maxm, cycle[maxn], lc;
void dfs(int remain, int k)
{
	if (p[k] > remain) {
		int m = 1;
		for (int i = 0; i < k; ++i)
			if (step[i])
				m *= step[i];
		if (m > maxm)
		{
			maxm = m;
			lc = 0;
			for (int i = 0; i < k; ++i)
				if (step[i])
					cycle[lc++] = step[i];
			while (remain--)
				cycle[lc++] = 1;
		}
	} else {
		step[k] = 0;
		dfs(remain, k + 1);
		for (step[k] = p[k]; step[k] <= remain; step[k] *= p[k])
			dfs(remain - step[k], k + 1);
	}
}
int main()
{
	make();
	int T, n;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		maxm = 1, lc = 0;
		if (n == 1)
			cycle[lc++] = 1;
		else
			dfs(n, 0);
		sort(cycle, cycle + lc);
		printf("%d", maxm);
		int k = 1, tmp;
		for (int i = 0; i < lc; ++i)
		{
			tmp = k++;
			for (int j = 1; j <= cycle[i] - 1; ++j)
				printf(" %d", k++);
			printf(" %d", tmp);
		}
		printf("\n");
	}
	return 0;
}