CF1220D Alex and Julian

Codeforces

Luogu

洛谷那个翻译有毒吧...题意都讲错了... 然后我想了半天不会做

分析

考虑两个数 $a,b$ 要满足什么条件才可以同时留下。

可以发现,$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环,这个环的大小是

$$ \frac{\operatorname{lcm}(a,b)}{a}+\frac{\operatorname{lcm}(a,b)}{b} $$

要使图是二分图,则不能存在奇环,因此有

$$ \frac{\operatorname{lcm}(a,b)}{a}+\frac{\operatorname{lcm}(a,b)}{b}\equiv 0\pmod 2 $$

$$ \frac{a+b}{\gcd(a,b)}\equiv 0\pmod 2 $$

显然可以根据 $a,b$ 的奇偶性进行讨论:

  • 若 $a,b$ 都为奇数,则上式显然成立。
  • 若 $a,b$ 一奇一偶,则上式显然不成立。
  • 若 $a,b$ 都为偶数,可以约掉一个 $2$ 的幂转化成上面两种情况。

综上,如果 $a,b$ 的二进制末尾的 $0$ 的数量相同,则 $a,b$ 可以同时留下。

那么这题就很简单了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,o[60]; ll a[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i]=read(),++o[__builtin_ctzll(a[i])];
    int ans=0;
    for (re int i=1;i<60;++i)
        if (o[i]>o[ans]) ans=i;
    printf("%d\n",n-o[ans]);
    for (re int i=1;i<=n;++i)
        if (__builtin_ctzll(a[i])!=ans) printf("%lld\n",a[i]);
    return 0;
}
最后修改:2019 年 11 月 03 日 05 : 25 PM

发表评论