Codeforces Round 949

题面见 Codeforces Round 949

D. Turtle and Multiplication

Turtle 刚刚在数学课上学会了如何乘法两个整数，他非常兴奋。

然后 Piggy 给了他一个整数 $n$，并让他构造一个序列 $a_1,a_2,\dots ,a_n$，该序列满足以下条件：

• 对于所有 $1\le i\le n$，$1\le a_i\le 3\cdot {10}^5$。
• 对于所有 $1\le i<j\le n-1$，$a_i\cdot a_{i+1}\ne a_j\cdot a_{j+1}$。

在所有满足上述条件的序列中，Piggy 要求 Turtle 找到一个不同元素数量最小的序列。

Turtle 显然无法解决这个问题，所以请帮帮他！

只需要考虑所有元素都是质数的情况。这是因为，如果所有元素都是质数，那么我们只需要保证任意相邻项对应的无序二元组各不相等（这里的不相等指的是，无序二元组 $(a,b)$ 和 $(c,d)$ 满足 $\mathrm{\neg }((a=c\wedge b=d)\vee (a=d\wedge b=c))$）即可，而如果存在非质数，要满足这个要求仍然需要满足这个约束，并且还需要满足更复杂的条件，会导致需要的不同元素的个数更多.

假设我们已经选取了 $k$ 个互不相等的质数，考虑能构造多长的序列.

设这些质数为 $p_0,p_1,\cdots ,p_{k-1}$，我们建一个无向图 $G=(V,E)$，其中

$$V=\{0,1,\cdots ,k-1\}$$$$E=\{⟨0,0⟩,⟨0,1⟩,\cdots ,⟨0,k-1⟩,⟨1,1⟩,⟨1,2⟩,\cdots ,⟨1,k-1⟩,\cdots ,⟨k-1,k-1⟩\}$$

也就是点集 $V$ 的完全无向图加上每个顶点的自环.

我们要寻找这样的路径，这个路径经过这个图的尽可能多的边，且每条边最多经过 1 次.

显然这个路径是这个图中删除一些边后形成的新的图的欧拉路径.

我们需要求最长的路径.

当 $k$ 是奇数时，我们发现每个点的出度和入度都是偶数，因此整个图必然存在欧拉路径，这样我们就经过了所有的边，路径的边数是

$$k+(k-1)+\cdots +1=\frac{k(k+1)}{2}$$

CAUTION

• 无向图中，一个自环会给一个结点带来 $2$ 的度数.

当 $k$ 是偶数时，我们发现每个点的出度和入度都是奇数，而一个图如果要存在欧拉路径，奇数度点最多 2 个。删除一条边可以减少最多 $2$ 个奇数点，因此我们至少要删除 ${\displaystyle \frac{k}{2}-1}$ 条边。删除下面的边：

$$⟨1,2⟩,⟨3,4⟩,\cdots ,⟨k-3,k-2⟩$$

这样，这个图中恰有 2 个奇数度点，这两个点分别为这个欧拉路径的起点和终点。我们得到了一个具有欧拉路径的图，路径的边数是

$$\frac{k(k+1)}{2}-(\frac{k}{2}-1)=\frac{k^2}{2}+1$$

因此，对于 $k$ 个互不相等的质数，能构造出的路径的边数是

$$f\left(k\right)=\{\begin{array}{l}\frac{k(k+1)}{2},k\text{ 是奇数}\\ \frac{k^2}{2}+1,k\text{ 是偶数}\end{array}$$

构造出的序列的长度，即路径的点数是

$$g\left(k\right)=f\left(k\right)+1=\{\begin{array}{l}\frac{k(k+1)}{2}+1,k\text{ 是奇数}\\ \frac{k^2}{2}+2,k\text{ 是偶数}\end{array}$$

只需要求出最小的正整数 $k$ 使得 $g\left(k\right)\ge n$. 因为 $g\left(k\right)$ 关于 $k$ 单调增加，所以可以用二分法实现. （当然也可以用数学硬解）

当确定 $k$ 后，我们直接跑 Hierholzer 算法就可以得到路径，然后我们随便找 $k$ 个质数就可以求出答案了。质数可以预处理一下，防止重复计算.

这里，我们 $k$ 不会超过 1415，而从小到大第 1415 个质数是 $11807<3\cdot {10}^5$，符合题意.

细节请见代码.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

std::vector<int> Hierholzer(const std::vector<std::vector<int>> &g) {
    int n = (int)g.size();
    if (n == 0) {
        return {};
    }
    std::vector<std::map<int, int>> num(n, std::map<int, int>());
    for (int u = 0; u < n; ++u) {
        for (int v : g[u]) {
            ++num[u][v];
        }
    }
    int begin = 0;
    for (int u = 1; u < n; ++u) {
        if ((int)g[begin].size() == 0 && (int)g[u].size() != 0) {
            begin = u;
        } else if ((int)g[begin].size() % 2 != 1 &&
                   (int)g[u].size() % 2 == 1) {
            begin = u;
        }
    }
    std::vector<int> ans;
    std::vector<int> idx(n, 0);
    std::vector<int> st;
    st.push_back(begin);
    while (!st.empty()) {
        int u = st.back();
        if (idx[u] < (int)g[u].size()) {
            int v = g[u][idx[u]];
            if (num[u][v] > 0) {
                --num[u][v];
                --num[v][u];
                st.push_back(v);
            }
            ++idx[u];
        } else {
            ans.push_back(u);
            st.pop_back();
        }
    }
    std::reverse(ans.begin(), ans.end());
    return ans;
}

bool check(const std::vector<std::vector<int>> &g,
           const std::vector<int> &path) {
    int n = (int)g.size();
    int m = 0;
    std::vector<std::map<int, int>> num(n, std::map<int, int>());
    for (int u = 0; u < n; ++u) {
        for (int v : g[u]) {
            ++num[u][v];
            ++m;
        }
    }
    int ps = (int)path.size();
    for (int i = 0; i + 1 < ps; ++i) {
        int u = path[i];
        int v = path[i + 1];
        if (u < 0 || u >= n || v < 0 || v >= n || num[u][v] == 0) {
            return false;
        }
        --num[u][v];
        --m;
        --num[v][u];
        --m;
    }
    return m == 0;
}

long long calc(long long k) {
    if (k % 2 == 1) {
        return k * (k + 1) / 2 + 1;
    } else {
        return k * k / 2 + 2;
    }
}

std::vector<long long> get_primes(long long x) {
    std::vector<long long> res;
    std::vector<long long> vis(x + 1, 0);
    long long i = 2;
    while (i <= x) {
        if (!vis[i]) {
            res.push_back(i);
            for (long long j = i; j <= x; j += i) {
                vis[j] = 1;
            }
        }
        ++i;
    }
    return res;
}

std::vector<long long> primes = get_primes(11807);

void solve() {
    int n;
    std::cin >> n;
    int l = 1, r = n;
    while (l < r) {
        int m = (l + r) / 2;
        if (calc(m) >= n) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    int k = l;
    std::vector<std::vector<int>> g(k, std::vector<int>());
    if (k % 2 == 1) {
        for (int i = 0; i < k; ++i) {
            for (int j = i; j < k; ++j) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    } else {
        for (int i = 0; i < k; ++i) {
            for (int j = i; j < k; ++j) {
                if (i % 2 == 1 && i >= 1 && i <= k - 3 && j == i + 1) {
                    continue;
                }
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    auto v = Hierholzer(g);
    // assert(check(g, v));
    for (int i = 0; i < n; ++i) {
        std::cout << primes[v[i]] << " \n"[i == n - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}