自动搬运

查看原文

来自洛谷，原作者为

	Fuyuki 闲云遮月，清风袭花

搬运于2025-08-24 21:57:52，当前版本为作者最后更新于2020-02-23 09:39:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于 $b$ 较小的情况 $(b\leq 150)$，可以暴力解决。

对于 $b$ 较大的情况，设 $x$ 等于小于 $\sqrt[3]{b}$ 的最大质数，$y$ 等于大于 $\sqrt{b}$ 的最小质数。

显然存在一个 $k=3$ 的方案 $xy\ xy\ xy$。

如果贪心的话，会第一步选出 $x^3$，而因为 $y^2>b$，所以会得到一个 $k=4$ 的方案 $y\ y\ y\ x^3$。

如果 $b$ 不够大，则可能出现 $x^2y<b$ 的情况，导致构造错误，因此需要一个简单的数据分治。

暴力的时候从大到小枚举会快很多。

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
const int N=2e6+1;
int T,n=N-1,m,p;
int tag[N],pri[N],pre[N],nxt[N];
I count(int x){
	if(x==1)return 1;
	ROF(i,n-1,1)if(x%i==0)
		return count(x/i)+1;
}
V force(){
	ROF(i,n-1,1)ROF(j,n-1,i)ROF(k,n-1,j)
		if(count(i*j*k)>4)
			return void(cout<<3<<' '<<i<<' '<<j<<' '<<k<<'\n');
	puts("-1");
}
V cheat(){
	int x=floor(cbrt(n)),y=ceil(sqrt(n)),z=pre[x]*nxt[y];
	cout<<3<<' '<<z<<' '<<z<<' '<<z<<'\n';
}
int main(){
	FOR(i,2,n){
		if(!tag[i])pri[++m]=i;
		FOR(j,1,m){
			if((p=i*pri[j])>n)break;
			tag[p]=1;
			if(i%pri[j]==0)break;
		}
	}
	FOR(i,1,n)pre[i]=pre[i-1],(!tag[i])&&(pre[i]=i);
	ROF(i,n,1)nxt[i]=nxt[i+1],(!tag[i])&&(nxt[i]=i);
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);
		if(n<=150)force();
		else cheat();
	}
}