题解：P4359 [CQOI2016] 伪光滑数

Little_Fox_Fairy · 2025-11-20 21:50:37 · 题解

Super Piano's Trick。

发现小于等于 128 的质数只有 31 个，所以我们考虑对于每一个质数先钦定它为最大质数，然后再考虑替换。

我们对于一个质数，初始值显然是 p_i^k ， p_i 指的是这个质数， k 满足是最大的一个 k 使得 p_i^k \le n 。

正确性显然，因为把小的替换成大的 p_i^k 无变化，但总代价变大。

然后我们每取出一个数，考虑将其中的一个最大的 p_i 替换为另一个小的质数，由于我们考虑了所有的质数，所以这个东西是不重不漏的。

Code

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define pb push_back 
#define eb emplace_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++) 
#define Rep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
namespace fast_IO {
    Fast_IO...
} using namespace fast_IO;
const int N=2e5+10;

int n,m,e[N];
int prime[N],cnt;
bitset<N> vis;
void init(int up) {
    rep(i,2,up) {
        if (!vis[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt and prime[j]*i<=up;j++) {
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
    return ;
}
struct node {
    int val,p,k,up;
    inline bool operator < (const node &a) const {
        return val<a.val;
    }
};
priority_queue<node> q;
signed main() {
    cin>>n>>m;
    init(128);
    rep(i,1,cnt) {
        int tmp=prime[i],tot=1;
        while (tmp<=n) {
            q.push({tmp,prime[i],tot,i-1});
            tot++,tmp*=prime[i];
        }
    }
    while (m--) {
        auto [val,p,k,up]=q.top();q.pop();
        if (!m) {
            cout<<val<<endl;
            return (0-0);
        }
        if (k>1) rep(i,1,up) q.push({val/p*prime[i],p,k-1,i});
    }
    return (0-0);
}