设 (p(x)) 为 (x) 的所有素因子乘积。
询问 (x) 的结果等于询问 (p(x)) 的结果，因此只需要询问没有平方因子的数即可。这可以在给定的 (lceil 0.65n ceil) 次询问内完成。
考虑交互器怎么回答询问：
令（以下求和在 XOR 意义，即 (mod 2) 的向量下进行）
- (g(x) = [x in S]x)
- (h(x) = [p(x)=x]sum_{p(i)=x} g(x)) （即将贡献在 (p(i)) 处统计）
[egin{aligned}
A(n) &= sum_{i=1}^c [gcd(i, n) = 1]h(i)\
&=sum_{d mid n} mu(d) sum_{d mid j, j le c} h(j)
end{aligned}
]
因为求和是在 XOR 意义下进行的，且 (n) 无重因子（(mu e 0)），所以 (mu(d) equiv 1)，相当于先做（高维）后缀和再做（高维）前缀和。
考虑根据询问的结果，还原出 (h(x))。直接先做（高维）前缀差分再做（高维）后缀差分即可。
接着我们需要还原一组恰好 (c) 个元素的答案。
我们知道一组元素的 XOR 值，所以对每个值是否在集合中设变量，对 (log n) 位的值列方程（在 (mod 2) 意义下），用 Gauss 消元解出一组解。
一个 (h(x)) 等价类的大小最大可以达到 (260) 左右，解不一定是唯一的（当然这种情况很少出现），这时可以随机解出两组解，并使用压位背包找到可以符合个数限制的解。因为数据随机生成，类似于 (n = 0) 的极端情况是几乎不可能出现的，且解出的两组解一般差距不大，这样的随机方法在实践中可以很快找到一组答案。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <unistd.h>
using namespace std;
#define LOG(f...) fprintf(stderr, f)
#define DBG(f...) printf("%3d: ", __LINE__), printf(f)
// #define DBG(f...) void()
#define all(cont) begin(cont), end(cont)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
using ll = long long;
template <class T> void read(T &x) {
char ch; x = 0;
int f = 1;
while (isspace(ch = getchar()));
if (ch == '-') ch = getchar(), f = -1;
do x = x * 10 + (ch - '0'); while(isdigit(ch = getchar()));
x *= f;
}
template <class T, class ...A> void read(T &x, A&... args) { read(x); read(args...); }
const int N = 1000005;
const int SIZE = 270;
const int MAX_LEN = 40005;
using v2 = bitset<SIZE>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool np[1005];
int p[170], pc = 0;
void sieve(int n) {
for (int i = 2; i <= n; ++i) {
if (!np[i]) {
p[pc++] = i;
for (int j = i * 2; j <= n; j += i)
np[j] = true;
}
}
}
vector<int> s[N];
int xs[N];
int len;
int n, c;
vector<int> P;
bitset<MAX_LEN> avail, aug;
int pre[MAX_LEN];
v2 e[20], _t[20];
vector<int> s1[MAX_LEN], s2[MAX_LEN];
bool type[MAX_LEN];
pair<v2, bool> eliminate(int n) {
v2 sol;
static int var[20];
bool is_uniq = true;
memset(var, -1, sizeof(var));
for (int i = 0, j = 0; j < n && i < len; ++j) {
int l = -1;
for (int k = i; k < len; ++k)
if (e[k].test(j)) { l = k; break; }
if (l == -1) { is_uniq = false; sol.set(j, rng() & 1); continue; }
if (l != i) swap(e[l], e[i]);
var[i] = j;
for (int k = i + 1; k < len; ++k)
if (e[k].test(j)) e[k] ^= e[i];
++i;
}
for (int i = len - 1; i >= 0; --i)
if (~var[i]) sol.set(var[i], ((sol & e[i]).count() & 1) ^ e[i].test(n));
return {sol, is_uniq};
}
int cnt = 0;
bool solve() {
int sum = 0;
vector<int> uni_s;
memset(type, 0, sizeof(type));
avail.reset();
avail.set(0);
int cnt = 0;
for (int p : P) {
int n = s[p].size();
if (n == 1) {
if (xs[p]) {
++sum;
uni_s.push_back(p);
}
continue;
}
for (int b = 0; b < len; ++b) {
for (int i = 0; i < n; ++i)
e[b].set(i, (s[p][i] >> b) & 1);
e[b].set(n, (xs[p] >> b) & 1);
_t[b] = e[b];
}
auto [sol, uniq] = eliminate(n);
if (uniq) {
for (int i = 0; i < n; ++i)
if (sol.test(i))
++sum, uni_s.push_back(s[p][i]);
}
else {
auto to_vec = [&](const v2 &v) -> vector<int> {
vector<int> r;
for (int i = 0; i < n; ++i)
if (v.test(i)) r.push_back(s[p][i]);
return r;
};
s1[cnt] = to_vec(sol);
copy_n(_t, len, e);
s2[cnt] = to_vec(eliminate(n).first);
if (s1[cnt].size() > s2[cnt].size()) swap(s1[cnt], s2[cnt]);
sum += s1[cnt].size();
if (s1[cnt].size() == s2[cnt].size()) {
uni_s.insert(uni_s.end(), all(s1[cnt]));
continue;
}
aug = (avail << (s2[cnt].size() - s1[cnt].size())) & ~avail;
for (int i = aug._Find_first(); i != (int)aug.size(); i = aug._Find_next(i))
pre[i] = cnt;
avail |= aug;
++cnt;
}
}
if (c < sum || !avail.test(c - sum)) return false;
vector<int> res = move(uni_s);
for (int i = c - sum; i; i -= s2[pre[i]].size() - s1[pre[i]].size()) {
type[pre[i]] = true;
res.insert(res.end(), all(s2[pre[i]]));
}
for (int i = 0; i < cnt; ++i)
if (!type[i])
res.insert(res.end(), all(s1[i]));
for (int x : res)
printf("%d ", x);
putchar('
');
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
sieve(1000);
read(n, c);
len = __lg(n) + 1;
for (int i = 1; i <= n; ++i) {
int r = 1;
int num = i;
for (int j = 0; j < pc; ++j) {
if (num % p[j] == 0) {
r *= p[j];
do num /= p[j]; while (num % p[j] == 0);
}
}
if (num > 1) r *= num;
s[r].push_back(i);
}
for (int i = 1; i <= n; ++i)
if (!s[i].empty()) P.push_back(i);
printf("%d ", (int)P.size());
for (int x : P)
printf("%d ", x);
putchar('
');
fflush(stdout);
for (int p : P)
read(xs[p]);
for (int i = n / 2; i >= 1; --i)
if (!s[i].empty())
for (int j = i * 2; j <= n; j += i)
xs[j] ^= xs[i];
for (int i = 1; i <= n; ++i)
if (s[i].empty()) xs[i] = 0;
for (int i = n / 2; i >= 1; --i)
if (!s[i].empty())
for (int j = i * 2; j <= n; j += i)
xs[i] ^= xs[j];
assert(xs[1] == 0 || xs[1] == 1);
while (!solve());
return 0;
}