Codeforces Round 949 (Div. 2)D. Turtle and Multiplication（欧拉路径、线性筛、思维构造）

Problem - D - Codeforces

按照官方正解做即可，顺带存个jiangly板子。

 1 #include <bits/stdc++.h>
 2 
 3 using i64 = long long;
 4 std::vector<int> minp, primes;
 5 
 6 void sieve(int n) {
 7     minp.assign(n + 1, 0);
 8     primes.clear();
 9     
10     for (int i = 2; i <= n; i++) {
11         if (minp[i] == 0) {
12             minp[i] = i;
13             primes.push_back(i);
14         }
15         
16         for (auto p : primes) {
17             if (i * p > n) {
18                 break;
19             }
20             minp[i * p] = p;
21             if (p == minp[i]) {
22                 break;
23             }
24         }
25     }
26 }
27 
28 void solve() {
29     int n;
30     std::cin >> n;
31     
32     int m = 1;
33     while (n - 1 > (m % 2 == 1 ? m * (m + 1) / 2 : m * m / 2 + 1)) {
34         m++;
35     }
36     
37     std::vector<int> a;
38     a.reserve(n);
39     
40     std::vector g(m, std::vector<int>(m, 1));
41     std::vector<int> cur(m);
42     if (m % 2 == 0) {
43         for (int i = 1; i < m - 1; i += 2) {
44             g[i][i + 1] = g[i + 1][i] = 0;
45         }
46     }
47     
48     auto dfs = [&](auto &&self, int x) -> void {
49         for (int &i = cur[x]; i < m; i++) {
50             if (g[x][i]) {
51                 g[x][i] = g[i][x] = 0;
52                 self(self, i);
53             }
54         }
55         a.push_back(primes[x]);
56     };
57     dfs(dfs, 0);
58     
59     a.resize(n);
60     for (int i = 0; i < n; i++) {
61         std::cout << a[i] << " \n"[i == n - 1];
62     }
63 }
64 
65 int main() {
66     std::ios::sync_with_stdio(false);
67     std::cin.tie(nullptr);
68     
69     sieve(3E5);
70     
71     int t;
72     std::cin >> t;
73     
74     while (t--) {
75         solve();
76     }
77     
78     return 0;
79 }