自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 22:47:32，当前版本为作者最后更新于2023-05-16 08:51:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

$k$ 的理论上界显然是 $\left\lfloor\frac{n}{2} \right\rfloor$，因为 $1\sim n$ 中任意两个不同正整数的最大公约数至多为 $\left\lfloor\frac{n}{2} \right\rfloor$。

我们首先考虑能否构造一个排列达到这个上界。

将所有 $i$ 和 $2i\ (1\le 2i\le n)$ 连边，则我们得到了若干条链。将这些链依次相接即可，即：

$$(1,2,4,8,...),(3,6,12,...),(5,10,20,...),...$$

那如果 $k$ 比这个上界小呢？很简单，将 $(2k+1)\sim n$ 倒序接在 $1$ 后面以达到 “舍去” 这些数的效果，即：

$$(1,n,(n-1),...,(2k+1)),(2,4,8,...),(3,6,12,...),(5,10,20,...),... $$

当然，构造方案并不唯一。

时间复杂度为 $O(\sum n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
int main(){
	t = read();
	while (t --){
		n = read(),k = read();
		if (k > n / 2){puts("No"); continue;}
		puts("Yes"),printf("1 ");
		for (ll i = n;i >= k * 2 + 1;i -= 1) printf("%lld ",i);
		for (ll i = 1;i <= k * 2;i += 2) for (ll j = max(2ll,i);j <= k * 2;j *= 2) printf("%lld ",j);
		puts("");
	}
	return 0;
}