D. Turtle and Multiplication

给一个整数 $n(2\le n\le {10}^6)$ ，构造一个由满足以下条件的整数组成的数列 $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}$ .

在所有这些序列中，小猪要求乌龟找出具有最少个不同元素的序列。

Solution

欧拉路径/Hierholzer 算法

需要学习欧拉图相关知识, 注：这个部分比较冷门

欧拉图问题

要使得 $a_i\cdot a_{i+1}\ne a_j\cdot a_{j+1}$，只要 $a_i$ 都取素数。这样只要满足 $(a_i,a_{i+1}),(a_j,a_{j+1})$ 是不同的即可(即经过不重复的边)。

将 $(a_i,a_{i+1})$ 看作是图的一条边，则问题变为找到点数最小的无向完全图(加上自环 $(a_i=a_{i+1})$)，使得这个图存在一条经过 $(n-1)$ 条边且不经过重复边的路径。

若完全图的点数为 $m$ 。(这时确定了点数，需要使得边数尽可能大)

• 若 $m$ 为奇数，则每个点的度数都是偶数，则一定存在欧拉路径，路径则为边数 $\frac{m(m+1)}{2}$

• 若 $m$ 为偶数，则每个点的度数都为奇数，这个时候需要删除一些边至少保证有欧拉通路，最多只能剩下两个奇数度数的点，所以至少要删除 $\frac{m}{2}-1$ 条边，路径长度为 $\frac{m(m+1)}{2}-\frac{m}{2}+1=\frac{m^2}{2}+1$

若当 $n={10}^6$ 时， $m\approx 1415$，第 $m$ 个素数是 $11807\le 3\times {10}^5$，满足要求。

所以这时只需要确定最小的 $m$，再跑一遍欧拉通路即可。

对于最小的 $m$，满足：
$m\equiv 1(mod2)\{\begin{array}{ll}n-1& \le \frac{m(m+1)}{2}\\ n-1& >\frac{(m-1)m}{2}\end{array}m\equiv 0(mod2)\{\begin{array}{ll}n-1& \le \frac{m^2}{2}+1\\ n-1& >\frac{(m-1{)}^2}{2}+1\end{array}$

代码：

void solve() {
    int n;
    cin >> n;

    int m = 1;
    while (n - 1 > (m % 2 == 1 ? m * (m + 1) / 2 : m * m / 2 + 1)) {
        m++;
    }

    vector<int> a;
    a.reserve(n);

    vector<vector<int>> g(m, vector<int>(m, 1));
    vector<int> cur(m);
    if (m % 2 == 0) {
        for (int i = 1; i < m - 1; i += 2) {
            g[i][i + 1] = g[i + 1][i] = 0;
        }
    }

    auto dfs = [&](auto&& self, int x) -> void {
        for (int& i = cur[x]; i < m; i++) {
            if (g[x][i]) {
                g[x][i] = g[i][x] = 0;
                self(self, i);
            }
        }
        a.push_back(primes[x]);
        };
    dfs(dfs, 0);

    a.resize(n);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

这里需要用到筛法；
!模板整理