P9345 夕阳西下几时回 题解

· · 题解

题意

构造一个由 1 \sim n 的排列组成的环，使得环上所有相邻元素的最大公约数组成的（不可重）集合中，有 k 个元素。

思路

构造数列：由一个给定数开始，第 i 项（i > 1）是第 i - 1 项的两倍（x, 2x, 4x, 8x, 16x ...），易得长度为 n 的这样的数列，共可以贡献 n - 1 个两两不同的最大公约数。

这样的数列第 i 项与第 i + 1 项的最小公倍数为 i，且设第一项为 a，则每一项都可以表示成 a \times 2^n 的形式，a 不同（且不互为倍数），则由它开头的两个序列中元素两两不同，贡献的最大公因数两两不同。

那么我们可以将许多这样的数列拼起来组成答案。

具体操作是：

证明

为什么这样处理，最后的那些未被使用的数从小到大输出不会形成新的最大公约数？

考虑“从小到大寻找下一个未被使用的数”的过程，易得找到的一定是下一个奇数，所有偶数都已经被包含在之前的数列中，而未被当做（后一项是前一项两倍的）数列开始元素的奇数一定没有被使用过。如果生成一半时，因已经满足了最大公因数个数要求而停止，那么会剩下一些未使用的偶数，而这些偶数一定不会小于最后的数列里的那个奇数，那么这些偶数的前和后必定有与之相邻的奇数，相邻数都互质，相邻奇数都互质，所以不会产生新的最大公约数。

为什么这样可以构造出最优解？如何证明没有更优的做法？

首先，给定 k、n，使此问题有解的必要条件是 k \leq \frac {n} {2}。因为 [\frac {n} {2} + 1, n] 之间的数不可能是两个 [1,n] 内的不同的数的 \operatorname{gcd}，若 x > y，则 \operatorname{gcd} (x,y)≤ \frac {x} {2}。而题目中相应的 x 最大可以取到 n，那么两个不同的数 \operatorname{gcd} 最大为 \frac {n} {2} ，所以最多有 \frac {n} {2} 个不同的 \operatorname{gcd}。

那么为什么这样的做法可以把 0 \sim \frac {n} {2} 的解都构造出来呢？我们观察排列中每个“数列”的特征，若数列长为 n，则会产生 n - 1 个新的 \operatorname{gcd}，而数列中正好有 n - 1 个偶数，可以看做有几个偶数，就可以产生几个不同的 \operatorname{gcd}。因为 1 \sim n 中任何数都可以被表示为一个奇数 k \times 2 ^ n 的形式，所以极端情况下，排列中所有数都被用作生成（后一项是前一项两倍的）数列，而 1 \sim n，共有 \lfloor \frac {n} {2} \rfloor 个偶数，也就可以最多生成这么多个不同的 \operatorname{gcd}。

代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
const int N = 3e5 + 5;
bool a[N];  //标记某数是否使用过的数组
vector<int> ans;    //答案序列

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ans.clear();
        int n, k;
        cin >> n >> k;
        int cnt = 0;
        memset(a, 0, (n + 1) * sizeof(bool));
        k--;    //先把 1 作为最大公约数的情况减去
        ans.push_back(1);   //把 1 放在序列开头
        a[1] = true;
        for (int i = 2; i <= n; i++) {
            if (cnt == k)
                    break;
            if (!a[i]) {
                a[i] = true;
                ans.push_back(i);
                for (int j = (i << 1); j <= n; j <<= 1) {
                    a[j] = true;
                    ans.push_back(j);
                    if (++cnt == k)
                        break;
                }
            }
        }
        if (cnt < k) {
            cout << "No\n";
            continue;
        } else
            cout << "Yes\n";
        for (int i : ans)
            cout << i << ' ';
        for (int i = 2; i <= n; i++)
            if (!a[i])
                cout << i << ' ';
        cout << '\n';
    }
    return 0;
}