Alex and Julian

Created by LXC on Fri Jun 30 14:57:14 2023

https://codeforces.com/problemset/problem/1220/D

ranting: 1900

tag: bitmasks, math, number theory

problem

现在有一个集合。在所有整数中，对于整数a和b的差值绝对值在集合中存在则a和b之间连接一条边。

你需要移除最少的元素使得集合可以将所有整数构成成一个二分图。

solution

最后的集合中的任意两个元素不存在2k倍数关系。

如果集合中只有奇数那么是合法的集合。

如果集合中同时存在奇数和偶数，那么一定不合法。图中会存在奇数条边的环就不是二分图，而奇数和偶数的最小公倍数是奇数。

对于只有偶数的集合，我们对这些数除以2，会产生一些奇数，这些奇数之间不存在2k倍数关系，在除以2之前也不存在2k倍数关系。

同样的，对于除以2后的偶数，我们再次除以2得到的奇数集合也可以构成一个合法解。

所以可以找到一个规律——集合中有相同2因子数目的数可以组成一个组。我们选择最大的一个组，将其他元素删除就行。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    cin >> n;
    vector<ll> cnt(100), a(n);
    ll mx = 0;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        ll c = 0;
        for (ll j = a[i]; j % 2 == 0; j >>= 1)
            c++;
        mx = max(mx, ++cnt[c]);
    }
    cout << n - mx << "\n";
    int p = 0;
    for (ll i : a) {
        ll c = 0;
        for (ll j = i; j % 2 == 0; j >>= 1)
            c++;
        if (cnt[c] == mx) {
            p = c;
            break;
        }
    }
    for (ll i : a) {
        ll c = 0;
        for (ll j = i; j % 2 == 0; j >>= 1)
            c++;
        if (c != p) {
            cout << i << " ";
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}