题解：P8316 [CQOI2016] 伪光滑数 加强版

· · 题解

怎么题解全是左偏树，来发一个既简单常数又小的做法。

先考虑固定最大质数（假设是 397）时怎么做。

我们考虑这样一个质数表：

我们用红线表示选了这个数，上面显示的是所有质因子都选 397 的情况。

我们假设有一个指针在这里：

考虑移动这个指针来得到所有的答案。

每次有两种选择：

同时，为了避免重复，我们要保证当前指针所在列不能大于上一行选的位置（也就是说，选出的数的位置单调不增）。

为了保证最大质数固定，最后一行选的位置不能移动。

容易用堆维护这个过程。每次取出值最小的状态，进行以上两种扩展即可。

证明：

然后发现本题最大质因子不固定，把每一种最大质因子都加入初始状态即可。

时间复杂度 O(k\log k)，目前是本题和弱化版的最优解

代码：

constexpr int prs[]={397, 389, 383, 379, 373, 367, 359, 353, 349, 347, 337, 331, 317, 313, 311, 307, 293, 283, 281, 277, 271, 269, 263, 257, 251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2};

struct DATA{
    int p,   //最大质因子在质数表中的位置
        k,   //最大的数 k 满足 pow(prs[p],k) <= n
        las, //上一行的位置
        n,m; //指针坐标
    ll val;  //值
    friend bool operator<(const DATA& x,const DATA& y){return x.val<y.val;}
};

priority_queue<DATA> q;

signed main(){
    ll n;
    int k;
    cin>>n>>k;
    int tp=0;
    for(auto i:prs){
        ll j=1;
        int tot=0;
        while(__int128(j)*i<=n){
            j*=i,tot++;
            q.push({tp,tot,sizeof(prs)/sizeof(int)-1,1,tp,j});
        }
        tp++;
    }
    F(i,1,k-1){
        DATA d=q.top();
        q.pop();
        if(d.m<d.las&&d.n<d.k) q.push({d.p,d.k,d.las,d.n,d.m+1,d.val/prs[d.m]*prs[d.m+1]});
        if(d.m!=d.p&&d.n+1<d.k) q.push({d.p,d.k,d.m,d.n+1,d.p+1,d.val/prs[d.p]*prs[d.p+1]});
    }
    cout<<q.top().val<<endl;
    return 0;
}