自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 23:04:31，当前版本为作者最后更新于2024-09-29 15:40:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先若 $2m > n$ 最大价值就是 $n$，一个答案是：

$$1, 2, \ldots, m - 1, n, m, m + 1, \ldots, n - 1$$

否则最大价值是 $n$ 的最大的 $\le m$ 的因数，设其为 $d$。一个答案是：

$$1 \sim d, 2d, d + 1 \sim 2d - 1, \ldots, n, n - d + 1 \sim n - 1 $$

最大价值是 $d$ 的证明：

显然一个排列的价值是 $n$ 的因数。因为前面已经给出了一个最大价值为 $d$ 的构造，所以只需要证 $n$ 的 $> m$ 的因数不可能成为一个排列的价值。

任取 $n$ 的一个 $> m$ 的因数，设其为 $x$。那么首先每个长度为 $m$ 的子段都一定要有一个 $x$ 的倍数。

若一个 $x$ 的倍数 $y$ 是一个长度为 $m$ 的子段的最大值，就称 $y$ 支配了这个子段。

可以发现 $x$ 最多只能支配 $x - m + 1$ 个子段，还剩下 $n - x$ 个子段需要支配。

显然一个数至多支配 $m$ 个子段，剩下的 $x$ 的倍数有 $\frac{n}{x} - 1$ 个。

因为 $(\frac{n}{x} - 1) \times m < (\frac{n}{x} - 1) \times x = n - x$，所以这些数不可能支配所有长度为 $m$ 的子段。

时间复杂度：每个测试用例 $O(n)$。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

void solve() {
	int n, m;
	scanf("%d%d", &n, &m);
	if (m * 2 > n) {
		for (int i = 1; i <= n; ++i) {
			int x = i;
			if (i == m) {
				x = n;
			} else if (i > m) {
				--x;
			}
			printf("%d%c", x, " \n"[i == n]);
		}
	} else {
		while (n % m) {
			--m;
		}
		for (int i = 1; i <= n; ++i) {
			int t = i;
			if (i > m && (i - 1) % m == 0) {
				t += m - 1;
			} else if (i > m) {
				--t;
			}
			printf("%d%c", t, " \n"[i == n]);
		}
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

闲话：这题一开始是 MX-X only 的 T1。