自动搬运

查看原文

来自洛谷，原作者为

	konyakest **

搬运于2025-08-24 22:37:56，当前版本为作者最后更新于2024-06-06 08:46:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

先考虑固定最大质数（假设是 $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;
}