题意
给出一个$n$个元素的集合$B$，以及节点为所有整数组成的图，对于两个整数$i,j$如果满足$|i-j| \in B$，那么$i,j$之间有一条无向边。
问至少删去$B$中多少个数，使得该图是一个二分图
数据范围：$1 \le n \le 200000,1 \le b_i \le 10^8$
题解
对于任意一个节点$u$，及$B$中的任意两个元素$x,y$，向后连边，会在节点$u+lcm(x,y)$处形成一个环，环的边数为$$\frac{lcm(x,y)}{x}+\frac{lcm(x,y)}{y}=\frac{x}{gcd(x,y)}+\frac{y}{gcd(x,y)}$$
而我们知道，判定二分图的条件为图中不存在奇环
若上式为奇数，则$x,y$不能同时存在；反之，若上式为偶数，则$x,y$能同时存在
我们将$x,y$的公约数中的$2$全部提出来，这时$gcd(x,y)$中没有约数$2$，$x'+y'$与原式奇偶性相同
这时$x'$与$y'$中至少有一个为奇数，若另一个也为奇数，则其和为偶数；否则其和为奇数，不能同时存在；而这在二进制上表示为$x,y$最低非零位相同
确定算法为在$B$中统计最低非零位相同的数的个数，取最大值，其余的需全部删去
代码：
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
typedef vector<LL>::iterator it;
const int N=200000+10;
int n;
LL b[N];
vector<LL> s[64];
int t;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
int j=0;
for(;!(b[i]>>j&1);j++);
s[j].push_back(b[i]);
}
for(int i=1;i<64;i++)
if(s[i].size()>s[t].size())
t=i;
printf("%d\n",n-s[t].size());
s[t].clear();
for(int i=0;i<64;i++)
for(it j=s[i].begin();j!=s[i].end();j++)
printf("%lld ",*j);
return 0;
}