题解 P4226 【避难所】

Fuyuki · 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();
    }
}