首先考虑怎样的集合一定是合法的
发现全部是奇数的集合一定合法，因为每次都是奇数连偶数，偶数连奇数
然后考虑如果集合同时有奇数和偶数是否一定不合法，结论是一定不合法，证明如下：
设某个奇数为 $2x+1$ ，某个偶数为 $2y$，那么 $0$ 到 $(2x+1)*(2y)$ 就有两种路线，$2x+1$ 步和 $2y$ 步的，
这两条路线刚好构成一个奇环，所以一定不是二分图
所以一种合法方案就是全留奇数，但是还不够，因为可能删掉一些奇数和偶数以后只剩下偶数也是合法的，比如 $2,6$ 就是合法的
发现如果只剩下偶数，那么我们可以把所有偶数同时除以 $2$，这样并不影响集合的性质，证明的话可以这样考虑：
所有数都是偶数的情况下，编号为偶数的点只会连向编号为偶数的点，奇数点也只能连奇数点，那么我们可以把这两种点分开来
然后重新按原编号大小编号为 $0,1,...$，其实就是偶数点的编号全部除以 $2$，奇数点的编号全部 $-1$ 再除以 $2$
发现这样新的两个图其实是一样的并且就是原集合的数都除以 $2$ 以后构成的图，所以证明完毕
然后除以二以后发现又有些奇数有些偶数了，继续递归地考虑即可
所以，可能的方案应该是这样的：
1. 全留奇数
2. 把1.奇数都扔了，然后全留/2后是奇数的数
3. 把1.2.的奇数都扔了，全留/4后是奇数的数
...
然后直接模拟即可，复杂度 $O(n log 10^{18})$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; ll n,a[100][N],ans=-1,p; int main() { n=read(); for(int i=1;i<=n;i++) a[0][i]=read(); for(int i=0;i<100;i++) { ll res=0; bool flag=0; for(int j=1;j<=n;j++) { if(a[i][j]&1) res++; if(a[i][j]) flag=1; } if(!flag) break; if(res>ans) ans=res,p=i; for(int j=1;j<=n;j++) { if(a[i][j]&1) a[i+1][j]=0; else a[i+1][j]=a[i][j]>>1; } } printf("%lld ",n-ans); for(int i=1;i<=n;i++) if((a[p][i]&1)==0) printf("%lld ",a[0][i]); if(n-ans) puts(""); return 0; }