1. 正确理解题意：
- 简述该题：
给定两个集合，(B={x,y,dots}),????(Z={整数集})。
如果集合 (Z) 中的两个元素 (i, j) 之差在集合 (B) 中,则有一条连接 (i, j) 的边。
现在要从集合 (B) 中删去一些元素，使得边所连成的图是一个二分图。
使得删去的元素尽可能少。
2. 思路及简单证明：
首先判断是不是二分图可以看图中是否有奇环。
考虑一个特殊的整数 (0)。
如果集合 (B) 中一个数 (a) 减去 (0) 所得还是 (a)。所以 (a) 和 (0) 之间有一条边。
若 (a) 的因数 (frac{a}{2}) 也在集合 %B% 中，那么 (0)，(a)，(frac{a}{2}) 之间形成一个奇环。
因此我们在选中 (a) 后要将其倍数和因数全部删除。
也就是说在 (0) 和 (a) 之间存在一个步数，步长是一个素数。我们走了 (x) 步从 (0) 到 (a)。
同理，我们也可以通过不同的步长和步数走到一个位置。现在假设两次都走到了 (lcm)。
只有我们两边步数相同时，链接起来才不是奇环。（链接的地方在 (lcm)）
3. 实现：
(mathcal{AC}) 代码：
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define int long long
#define ri register int
using namespace std;
int n, a[200010], cnt[200010];
map<int,int> mp;
map<int,int>::iterator ans;
signed main()
{
scanf("%lld", &n);
for (ri i=1; i<=n; i ) {
scanf("%lld", &a[i]);
int x=a[i];
while (x && x%2==0) {
cnt[i] ;
x/=2;
}
mp[cnt[i]] ;
}
int ansval=0;
for (map<int,int>::iterator it=mp.begin(); it!=mp.end(); it) {
if ((*it).second>ansval) {
ans=it;
ansval=(*it).second;
}
}
printf("%lldn", n-(*ans).second);
for (ri i=1; i<=n; i ) {
if (cnt[i]!=(*ans).first) {
printf("%lldn", a[i]);
}
}
return 0;
}
参考博客：