一道名副其实的 educational 的 hot tea。
首先看到我们将问题进行初步转化：我们先求出 \(\prod\limits_{i=1}^n(i!)\) 的质因数分解形式中，所有出现次数为奇数的质数，这个异常好办——因为 \(\prod\limits_{i=1}^n(i!)=\prod\limits_{i=1}^ni^{n-i+1}\)，因此 \(n-1,n-3,\cdots,n\bmod 2+1\) 在式子中的次数都是偶数我们可以把它们都踢掉，故 \(\prod\limits_{i=1}^ni!\) 质因数分解形式中，出现次数为奇数的质因子集合，就等于 \(n!!\) 中，出现次数为奇数的质因子的集合，预处理每个数的最小质因子后即可 \(n\log n\) 地分解。
于是问题转化为，求一个长度最小的序列 \(\{a_m\}\)，满足 \(1\le a_i\le n\)，且 \(\prod\limits_{i=1}^ma_i!\) 的质因数分解形式中，出现次数为奇数的质因子的集合等于 \(n!!\) 出现次数为奇数的质因子集合。到这里，我们不妨来发觉下性质：如果 \(n\) 是偶数，那么 \(n!!=2^{n/2}·(\dfrac{n}{2})!\)，前者将质数模 \(2\) 后要么剩个 \(2^0\)，要么剩个 \(2^1\)，因此 \(n!!\) 质因子为奇数的集合要么与 \((\dfrac{n}{2})!\) 相同，要么与 \(2·(\dfrac{n}{2})!\) 相同；同理，如果 \(n\) 是奇数，那么 \(n!!=\dfrac{n!}{(n-1)!!}=\dfrac{n!}{2^{(n-1)/2}·(\frac{n-1}{2})!}\)，因此 对于奇数 \(n\)，\(n!!\) 出现次数为奇数的集合要么与 \(n!·(\dfrac{n-1}{2})!\) 相同，要么与 \(2·n!·(\dfrac{n-1}{2})!\) 相同。
也就是说符合条件的长度最小的序列 \({a_m}\) 长度不超过 \(3\)。故我们考虑对 \(0,1,2\) 的情况分别求解，\(0\) 的情况直接特判掉即可，\(1\) 的情况就考虑哈希，我们给每个质因子赋上一个 \([1,2^{64}-1]\) 的随机权值，然后定义一个集合的权值为其中所有元素权值的 XOR，这样我们预处理出 \(1!,2!,\cdots,n!\) 的权值后，检验是否存在某个 \(i!\) 的权值等于 \(n!!\) 的权值，\(2\) 的情况也同理，map 预处理下每个权值出现的位置即可。
时间复杂度 \(n\log n\)。
mt19937 rng(20060729 ^ chrono :: steady_clock :: now().time_since_epoch().count());
template<typename T> T rand(T l, T r) {return uniform_int_distribution<T>(l, r)(rng);}
const int MAXN = 1e6;
int n, pr[MAXN / 2 + 5], prcnt = 0, vis[MAXN + 5], mnp[MAXN + 5];
int cnt[MAXN + 5], book[MAXN + 5];
u64 v[MAXN + 5], pre[MAXN + 5];
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) pr[++prcnt] = i, mnp[i] = i;
for (int j = 1; j <= prcnt && pr[j] * i <= n; j++) {
vis[pr[j] * i] = 1; mnp[pr[j] * i] = pr[j];
if (i % pr[j] == 0) break;
}
}
}
int main() {
scanf("%d", &n); sieve(MAXN);
for (int i = 1; i <= n; i++) if ((n - i + 1) & 1) {
int tmp = i;
while (tmp ^ 1) {
int p = mnp[tmp];
while (tmp % p == 0) tmp /= p, cnt[p] ^= 1;
}
}
bool flg = 1;
for (int i = 1; i <= n; i++) flg &= (!cnt[i]);
if (flg) {
printf("%d\n", n);
for (int i = 1; i <= n; i++) printf("%d%c", i, " \n"[i == n]);
return 0;
}
for (int i = 1; i <= n; i++) v[i] = rand(1ull, ULLONG_MAX);
u64 hs = 0;
for (int i = 1; i <= n; i++) if (cnt[i]) hs ^= v[i];
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1]; int tmp = i;
while (tmp ^ 1) {
int p = mnp[tmp];
while (tmp % p == 0) tmp /= p, pre[i] ^= v[p];
}
}
for (int i = 1; i <= n; i++) if (pre[i] == hs) {
printf("%d\n", n - 1);
for (int j = 1; j <= n; j++) if (j != i) printf("%d ", j);
return 0;
}
unordered_map<u64, int> pos;
for (int i = 1; i <= n; i++) {
if (pos[pre[i] ^ hs]) {
int X = i, Y = pos[pre[i] ^ hs];
printf("%d\n", n - 2);
for (int i = 1; i <= n; i++) if (i != X && i != Y)
printf("%d ", i);
return 0;
}
pos[pre[i]] = i;
}
printf("%d\n", n - 3);
for (int i = 1; i <= n; i++) if (i != 2 && i != (n >> 1) && i != n)
printf("%d ", i);
return 0;
}