题解：P4359 [CQOI2016] 伪光滑数

Super Piano's Trick。

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

我们对于一个质数，初始值显然是

p_i^k

，

p_i

指的是这个质数，

k

满足是最大的一个

k

使得

p_i^k \le n

。

正确性显然，因为把小的替换成大的

p_i^k

无变化，但总代价变大。

然后我们每取出一个数，考虑将其中的一个最大的

p_i

替换为另一个小的质数，由于我们考虑了所有的质数，所以这个东西是不重不漏的。

Code

CPP

#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);
}

题解：P4359 [CQOI2016] 伪光滑数

文章操作

相关推荐

评论

题解：P4359 [CQOI2016] 伪光滑数