Codeforces 1220 D - Alex and Julian

题意： 给定一个长度为 $n$n的序列 $B$B，对于任意的整数，当 $\mid i-j\mid$∣i−j∣属于 $B$B时，点 $i$i和点 $j$j之间会连一条边，问至少删除 $B$B中多少元素可以使得所有整数形成的图是一个二分图

题解： 二分图的性质：一个图为二分图当且仅当图中不存在奇数环。
那么借助这个性质，我们先考虑将当前符合条件的整数，即两个整数差的绝对值在 $B$B中存在时，将其连上一条边。那么对于存在于 $B$B中的两个点 $a$a和 $b$b，可以看成两者分别从 $0$0开始后，以每次走 $a$a步和 $b$b步往前走，那么两者第一次相遇就是在 $lcm(a,b)$lcm(a,b)处（第 $2$2次，第 $3$3次 $\cdots$⋯都可以看成以前一次相遇处为起点再往后走 $lcm(a,b)$lcm(a,b)的总步数）。
此时以步幅 $a$a和步幅 $b$b前进分别走了 $\frac{lcm(a,b)}{a}$alcm(a,b)​和 $\frac{lcm(a,b)}{b}$blcm(a,b)​次，化简下得到：以步幅 $a$a走了 $\frac{b}{gcd(a,b)}$gcd(a,b)b​次，以步幅 $b$b走了 $\frac{a}{gcd(a,b)}$gcd(a,b)a​步。

由于不能形成奇数环，故要使得 $\frac{b}{gcd(a,b)}+\frac{a}{gcd(a,b)}\equiv 0\left(mod2\right)$gcd(a,b)b​+gcd(a,b)a​≡0(mod 2)

那么问题就转换成了两种情况：
$1.\frac{b}{gcd(a,b)}$1. gcd(a,b)b​和 $\frac{a}{gcd(a,b)}$gcd(a,b)a​都为奇数

$2.\frac{b}{gcd(a,b)}$2. gcd(a,b)b​和 $\frac{a}{gcd(a,b)}$gcd(a,b)a​一奇一偶

$\ast \frac{b}{gcd(a,b)}$∗ gcd(a,b)b​和 $\frac{a}{gcd(a,b)}$gcd(a,b)a​都为偶数是不可能的，
因为都为偶数就说明两者分母还可以继续除 $2$2，那么分母就不是 $gcd$gcd了

我们要求的是什么样的情况下使得图为二分图，即使得图中不存在奇数环，那么一奇一偶显然不成立。那么要求的便是两者都为奇数的情况。
由于要尽量少删除数，将 $B$B中所有数写成 $2^k\ast v$2k∗v， $v$v是一个奇数。那么只有当两个数的 $k$k相等时，
$\frac{b}{gcd(a,b)}$ gcd(a,b)b​和 $\frac{a}{gcd(a,b)}$gcd(a,b)a​才会都为奇数。
所以保留下来的即写成 $2^k\ast v$2k∗v后， $2^{0\sim 63}$20∼63数最多的幂。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
ll q[N], n;
vector<ll> ans[64]; 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &q[i]);
		int cnt = 0; ll x = q[i];
		while(x % 2 == 0) cnt++, x /= 2;
		ans[cnt].push_back(q[i]);
	}
	
	int Ma = 0;
	for(int i = 0; i < 64; i++)
		if((int)ans[i].size() > (int)ans[Ma].size()) Ma = i;
	
	printf("%d\n", n - (int)ans[Ma].size());
	for(int i = 0; i < 64; i++) { 
		if(i == Ma) continue;
		int len = (int)ans[i].size();
		for(int j = 0; j < len; j++)
			printf("%lld ", ans[i][j]);
	} 
	
	return 0;
}