自动搬运

查看原文

来自洛谷，原作者为

	zhanghuanrui 网名 Silvefish | We are preparing for the world of tomorrow.

搬运于2025-08-24 23:06:21，当前版本为作者最后更新于2025-05-21 11:06:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P11314 [RMI 2021] 礼物 / Present 题解

一个正整数集合 $S$ 是好的当且仅当 $\forall a,b \in S$，$\gcd(a,b) \in S$。定义 $S$ 的权值为 $\sum\limits_{a \in S} 2^{a-1}$。求出权值第 $k$ 小的好的集合。$k \le 1.5 \times 10^9$。

在这个数据范围下，我们可以感觉到答案集合的最大值并不会太大。因此，我们可以尝试直接把答案搜出来。具体地，假设答案集合的最大值为 $m$，可以从 $m$ 到 $1$ 依次考虑不选 / 选的情况，找出其中权值第 $k$ 小的集合。

不过，显然 $O(ans)$ 的搜索算法是行不通的。

我们考虑在选完较大的数之后，这些已经确定选的数对那些还没确定要不要选的数产生的限制。这时候，我们就会发现，不同的大数选择情况对小数的限制可能是相同的。例如，假设大于 $2$ 的数都已经确定选不选，那么大数集合是 $\{7,3\}$ 和 $\{5,3\}$ 对 $1$ 和 $2$ 的限制是一样的：$2$ 可选可不选，$1$ 必须要选。这就给了我们降低复杂度的机会。

具体地，可以发现，我们在考虑 $x$ 要不要选的时候，如果大于 $x$ 的选的数中 $x$ 的倍数的最大公因数等于 $x$，那么 $x$ 就必须要选（这是显然的）；否则，$x$ 可选可不选，因为就算没选 $x$，用集合里其它的数取最大公因数也不会得到 $x$，因此不违反题目要求。

因此，搜索的时候就只需要记录：所有还没有确定选不选的数中，已经确定要选的数中它们的倍数的最大公因数是多少。对于一个还没有确定选不选的数 $x$，这个值只有 $\lfloor\frac{m}{x}\rfloor+1$ 种不同的取值（因为可以为 $0$）。同时可以发现，如果 $\lfloor\frac{m}{x}\rfloor \le 2$，记录这个值是没有意义的，因为无论如何都不会违反题目规定。

我们在记忆化搜素的时候，记录 $(x,msk)$ 表示当前正在考虑选不选 $x$，并且上文所述的状态为 $msk$（可以用变进制数压成一个整数）时，剩下 $x$ 到 $1$ 这些数有多少种选法。此时总状态数大概是 $\sum\limits_{x=1}^{m} \prod \limits_{i=1}^{\min(x-1,\lfloor\frac{m}{3}\rfloor)} (\lfloor\frac{m}{i}\rfloor+1)$ 的。转移也很简单，枚举 $x$ 选不选，如果选就用 $x$ 更新一下 $msk$ 再递归到 $x-1$。

预处理结束后，对于一个给定的 $k$ 求答案也很简单。还是从大往小考虑选不选，优先不选，如果不选的方案数小于等于 $k$，答案集合就没有这个数；否则就有这个数。这样求一次答案是 $O(m^2)$ 的（因为更新 $msk$ 要 $O(m)$ 时间）。

如果你写完代码去跑一遍极限数据，就会发现答案集合的最大值不超过 $m=37$。虽然将其带入上面的公式，算出来状态数是 $1.3 \times 10^{12}$，但是有非常多的状态是不能同时取到的，例如在 $1$ 的倍数的最大公因数为 $4$ 时 $2$ 的倍数的最大公因数为 $2$。具体测试后发现状态数只有 $594228$ 种，可以轻松通过。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n=37,m=n/3,k;
int gcd[45][45];
int bas[20];
unordered_map<int,int> mp[45];
//msk[i] : 目前选的数中 i 的倍数的所有数的 gcd 是 i 的几倍
int dfs1(int x,int msk)
{
	if(!x) return mp[x][msk]=1;
	if(mp[x].count(msk)) return mp[x][msk];
	int ret=0,_=msk;
	if(x>m || msk/bas[x-1]%(n/x+1)!=1) ret+=dfs1(x-1,msk);
	for(int i=1;i<=m;i++)
	{
		if(x%i) continue;
		int k=msk/bas[i-1]%(n/i+1);
		msk-=k*bas[i-1];
		k=gcd[k][x/i];
		msk+=k*bas[i-1];
	}
	ret+=dfs1(x-1,msk);
	mp[x][_]=ret;
	return mp[x][_]=ret;
}
vector<int> dfs2(int x,int msk,int rem)
{
	if(!x) return vector<int>();
	if(x>m || msk/bas[x-1]%(n/x+1)!=1)
	{
		int tmp=mp[x-1][msk];
		if(tmp>rem) return dfs2(x-1,msk,rem);
		rem-=tmp;
	}
	for(int i=1;i<=m;i++)
	{
		if(x%i) continue;
		int tmp=msk/bas[i-1]%(n/i+1);
		msk-=tmp*bas[i-1];
		tmp=gcd[tmp][x/i];
		msk+=tmp*bas[i-1];
	}
	vector<int> ret=dfs2(x-1,msk,rem);
	ret.push_back(x);
	return ret;
}
void solve()
{
	scanf("%lld",&k);
	vector<int> ans=dfs2(n,0,k);
	printf("%lld ",(int)ans.size());
	for(int x:ans) printf("%lld ",x);
	printf("\n");
}
signed main()
{
	for(int i=0;i<=40;i++) for(int j=0;j<=40;j++) if(i|j) gcd[i][j]=__gcd(i,j);
	for(int i=bas[0]=1;i<=m;i++) bas[i]=bas[i-1]*(n/i+1);
	dfs1(n,0);
	int t;cin>>t;
	while(t--) solve();
}