Codeforces

分析

考虑两个数 $a,b$ 要满足什么条件才可以同时留下。

可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是
$$
\frac{\operatorname{lcm}(a,b)}{a}+\frac{\operatorname{lcm}(a,b)}{b}
$$
要使图是二分图，则不能存在奇环，因此有
$$
\frac{\operatorname{lcm}(a,b)}{a}+\frac{\operatorname{lcm}(a,b)}{b}\equiv 0\pmod 2
$$
即
$$
\frac{a+b}{\gcd(a,b)}\equiv 0\pmod 2
$$
显然可以根据 $a,b$ 的奇偶性进行讨论：

• 若 $a,b$ 都为奇数，则上式显然成立。
• 若 $a,b$ 一奇一偶，则上式显然不成立。
• 若 $a,b$ 都为偶数，可以约掉一个 $2$ 的幂转化成上面两种情况。

综上，如果 $a,b$ 的二进制末尾的 $0$ 的数量相同，则 $a,b$ 可以同时留下。

那么这题就很简单了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,o[60]; ll a[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i]=read(),++o[__builtin_ctzll(a[i])];
    int ans=0;
    for (re int i=1;i<60;++i)
        if (o[i]>o[ans]) ans=i;
    printf("%d\n",n-o[ans]);
    for (re int i=1;i<=n;++i)
        if (__builtin_ctzll(a[i])!=ans) printf("%lld\n",a[i]);
    return 0;
}