有一个 \(gcd\) 游戏，按以下步骤进行：
- 选择一个 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\) 。
- 对于每个 \(i\) ，\(d_i = gcd(p_i, p_{i \% n + 1})\)
- 排列 \(p\) 的 \(score\) 为数组 \([d_1, d_2, \cdots, d_n]\) 中不同数的个数。
给一个 \(n\) ，需要构造一个排列 \(p\) ，使得 \(score_p\) 最大。
\(key\) ：若一个数组中，任意 \(g = gcd(a_i, a_j)\) 存在，则数组中 \(2 \cdot g\) 存在。
- 推论：\(n\) 的排列中任选两个数可构造的 \(gcd\) 范围为 \([1, \frac{n}{2}]\) 。
如何让相邻两个数的 \(gcd\) 取遍 \([1, \frac{n}{2}]\) 。
考虑一个贪心做法： \(x | y\) 可以满足的条件之一为 \(y \geq 2x\) 。于是枚举所有奇数 \(i\) ，然后构造出一组连续的 \(i \cdot 2^k \leq n\) 。程序结束后 \(1 \sim n\) 都会出现一次，且 \([\lfloor \frac{n}{2} \rfloor + 1, n]\) 会出现在每组的最后一位。于是 \(gcd\) 取遍 \(1, \lfloor \frac{n}{2} \rfloor\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n; std::cin >> n;
std::vector<int> ans;
for (int i = 1; i <= n; i += 2) {
for (int j = i; j <= n; j *= 2) {
ans.push_back(j);
}
}
for (int i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i == ans.size() - 1];
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}