CF1220D 题解
sgl654321
·
·
题解
题目大意
给定一个长度为 n 的序列 B，并以此来构造一张点集为正整数集的图。两个点 x, y 之间有连边当且仅当 |x-y|\in B。
问至少删除多少个 B_i 之后，构造出来的图是一张二分图。并给出删除方案。
解题思路
转化二分图判定
我们知道，一张图是二分图，等价于这张图没有长度为奇数的环。如果 B 中只有一个元素，那么这张图绝对不可能形成环。
$1+k\text{lcm}(x,y),k\in Z$ 肯定同时出现在两条链中，这就形成了一个环。该环的长度为 $\dfrac{\text{lcm}(x,y)}{x}+\dfrac{\text{lcm}(x,y)}{y}$。我们应当保证这个长度不能是奇数。
根据小学数学知识 $\text{lcm}(x,y)\times \gcd(x,y) =xy$，我们可以化简式子为：$\dfrac{x+y}{\gcd(x,y)}$，这个分式不能是奇数。
### 转化该分式不是奇数的判定
这个分式中，$x,y$ 满足什么关系，才能是偶数呢？
奇偶性质只与 $2$ 这个因子有关，因此我们可以提取出 $x,y$ 中 $2$ 这个因子的幂次。具体的，设 $x=2^{q_1}k_1,y=2^{q_2}k_2$，其中 $k_1,k_2$ 都是奇数，$q_1,q_2$ 为整数。
那么 $\gcd(x,y) = \gcd(2^{q_1}k_1,2^{q_2}k_2)=2^{\min(q_1,q_2)}\times \gcd(k_1,k_2)$。
这个分式就变成了：
$\dfrac{2^{q_1}k_1}{2^{\min(q_1,q_2)}\times \gcd(k_1,k_2)}+\dfrac{2^{q_2}k_2}{2^{\min(q_1,q_2)}\times \gcd(k_1,k_2)}$。
如果 $q_1\not=q_2$，那么这两项一定一个是奇数，一个是偶数，因为有一项 $2$ 除不尽。两者相加就变成奇数了，就形成了长度为奇数的环。
因此我们分析出，只有 $q_1=q_2$ 才能使该分式是一个奇数。
### 提取 $2$ 的幂次统计答案
所以，我们就要在 $B$ 中删除一些元素，使得剩下的元素，含有 $2$ 的幂次都相同。我们计算出 $B$ 中每一个元素含有 $2$ 质因子的个数，其中出现次数最多的那个个数就是我们要保留的。通过枚举，可以轻松求出答案。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define maxn 200100
using namespace std;
typedef long long ll;
ll n, a[maxn], cnt, b[maxn], now;
ll d[maxn], ma;
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i ++){
cnt = 0; now = a[i];
while(now % 2 == 0)
cnt ++, now /= 2;
b[i] = cnt;
d[cnt]++;
}
ma = 0;
for(int i = 0; i <= 100; i++)
if(d[i] > d[ma]) ma = i;
cout << n - d[ma] << endl;
for(int i = 1; i <= n; i++)
if(b[i] != ma) cout << a[i] << ' ';
cout << endl;
return 0;
}
```
虽然本题代码不长，但是思维量也并不大。中规中矩的一道 CF *1900。