gyara-ω

· · 题解

见到构造题……不如先写个暴力？

猜测答案最小为 n-3。那么我们拆开，变成求解能否去掉 0,1,2,3 个数之后使得 A' 是个平方集合。

先确定一个大体的思路。注意到平方集合，乘积在分解之后质因子的幂数都是偶数，那么幂数可以划归到 0 或者 1……这个东西有点类似于异或，那么几个阶乘的乘积质因数分解就相当于几个阶乘质因数分解之后幂次进行异或。

Motivation: 快速将几个阶乘质因数分解之后幂次进行异或。

考虑完善这个 Motivation，可以将每个质因子给定一个哈希值，这样一个数的质因数分解可以用其质因数分解后的所有质因子异或值表示。

那么问题就简单了。我们先求出 \displaystyle \prod_{i=1}^n i! 的哈希值，记作 k。记 f_i 为 i! 的哈希值。

去掉 0 个数

此时 k=0。判断即可。

去掉 1 个数

此时 k=f_i，O(n) 判断即可。

去掉 2 个数

考虑开一个 map 记下 f_i \to i 的映射，那么当 map 中存在 k \oplus f_p \to q 的时候，去掉 p,q 合法。

去掉 3 个数

显然去掉 2!,n!,\left\lfloor\dfrac{n}{2}\right\rfloor! 是合法的解（要找 Motivation 可以打表，去掉 3 个数的情况有 7,11,23）。

那么拼盘得正解。问题解决。

/*
他决定要“格”院子里的竹子。于是他搬了一条凳子坐在院子里，面对着竹子硬想了七天，结果因为头痛而宣告失败。
DONT NEVER AROUND . //
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0;
    char c=getchar();
    while(c<'0' || c>'9')   c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
    return x;
}
void write(int x)
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int cnt,prime[400005];
bool vis[1000005];
LL hsh[1000005],fac[1000005];
int n;
void shai(int up)
{
    uniform_int_distribution<LL> range(1,~(0llu));
    default_random_engine e(rand());
    vis[1]=true;
    for(int i=2;i<=up;++i)
    {
        if(!vis[i]) prime[++cnt]=i,hsh[i]=range(e);
        for(int j=1;j<=up && i*prime[j]<=up;++j)
        {
            vis[i*prime[j]]=true;
            hsh[i*prime[j]]=hsh[i]^hsh[prime[j]];
            if(i%prime[j]==0)   break;
        }
    }
    for(int i=2;i<=up;++i)  fac[i]=hsh[i]^fac[i-1];
}
unordered_map<LL,int> M;
int main(){
    srand(time(NULL));
    n=read();
    shai(n);
    LL val=0;
    for(int i=1;i<=n;++i)   val^=fac[i];
    if(val==0)
    {
        write(n),puts("");
        for(int i=1;i<=n;++i)   write(i),putchar(' ');
        return 0;
    }
    for(int i=1;i<=n;++i)
    {
        if(val==fac[i])
        {
            write(n-1),puts("");
            for(int j=1;j<=n;++j)   if(i!=j)    write(j),putchar(' ');
            return 0;
        }
    }
    for(int i=2;i<=n;++i)
    {
        if(M.find(val^fac[i])!=M.end())
        {
            int p=M[val^fac[i]],q=i;
            write(n-2),puts("");
            for(int j=1;j<=n;++j)   if(j!=p && j!=q)    write(j),putchar(' ');
            return 0;
        }
        M[fac[i]]=i;
    }
    write(n-3),puts("");
    for(int i=1;i<=n;++i)   if(i!=2 && i!=n && i!=n/2)  write(i),putchar(' ');
    return 0;
}