#include <bits/stdc++.h>
using namespace std;
const int ODD = 19;
const int EVEN = 18;
const int N = 38;
const int K = 1500000000;
bool good_odd[1 << ODD];
bool good_even[1 << EVEN];
int pre_gcd[N][N], cnt[1 << EVEN];
int match[1 << ODD];
void add(int &x, int y) {
if (x < K - y) x += y;
else x = K;
}
void solve() {
int k; cin >> k; k++;
int cur_odd = 0, cur_even = 0;
for (int d = N - 1; d > 0; d--) {
int t = (d - 1) / 2;
if (d & 1) {
if (cur_odd >> t & 1) continue;
} else {
if (cur_even >> t & 1) continue;
}
for (int nxt_even = 0; nxt_even < (1 << t); nxt_even++)
cnt[nxt_even] = good_even[nxt_even + cur_even];
for (int i = 0; i < t; i++)
for (int mask = 0; mask < (1 << t); mask++)
if (mask >> i & 1)
cnt[mask] += cnt[mask ^ (1 << i)];
int tmp = 0;
for (int nxt_odd = 0; nxt_odd < (1 << (d / 2)); nxt_odd++) {
if (!good_odd[cur_odd + nxt_odd]) continue;
int nxt_even = match[cur_odd + nxt_odd];
if ((nxt_even & cur_even) != cur_even) continue;
add(tmp, cnt[nxt_even & ((1 << t) - 1)]);
}
if (tmp < k) {
k -= tmp;
if (d & 1) cur_odd += 1 << t;
else cur_even += 1 << t;
for (int i = 0; i < ODD; i++)
if (cur_odd >> i & 1) {
int g = pre_gcd[2 * i + 1][d];
if (g & 1) cur_odd |= 1 << (g / 2);
else cur_even |= 1 << (g / 2 - 1);
}
for (int i = 0; i < EVEN; i++)
if (cur_even >> i & 1) {
int g = pre_gcd[2 * i + 2][d];
if (g & 1) cur_odd |= 1 << (g / 2);
else cur_even |= 1 << (g / 2 - 1);
}
}
}
vector<int> ans;
for (int i = 0; i < ODD; i++)
if (cur_odd >> i & 1)
ans.push_back(2 * i + 1);
for (int i = 0; i < EVEN; i++)
if (cur_even >> i & 1)
ans.push_back(2 * i + 2);
sort(ans.begin(), ans.end());
cout << ans.size();
for (int d : ans)
cout << ' ' << d;
cout << '\n';
}
int main() {
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
pre_gcd[i][j] = __gcd(i, j);
for (int mask = 0; mask < (1 << ODD); mask++) {
good_odd[mask] = true;
vector<int> bit;
for (int i = 0; i < ODD; i++)
if (mask >> i & 1)
bit.push_back(2 * i + 1);
for (int i : bit)
for (int j : bit)
if (~mask >> (pre_gcd[i][j] / 2) & 1)
good_odd[mask] = false;
for (int i = 0; i < EVEN; i++) {
match[mask] += 1 << i;
for (int j : bit)
if (~mask >> (pre_gcd[2 * i + 2][j] / 2) & 1) {
match[mask] -= 1 << i; break;
}
}
}
for (int mask = 0; mask < (1 << EVEN); mask++) {
good_even[mask] = true;
vector<int> bit;
for (int i = 0; i < ODD; i++)
if (mask >> i & 1)
bit.push_back(2 * i + 2);
for (int i : bit)
for (int j : bit)
if (~mask >> (pre_gcd[i][j] / 2 - 1) & 1)
good_even[mask] = false;
}
int t; cin >> t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
4128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
4128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
4128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
4128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
4128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
