CF1945 H GCD is Greater
什么鬼啊 div3 H diff: 2775。
纯属码力题。
首先发现 \(\gcd\) 肯定数字越多越小。
然后与值数字越多越小。
所以结论就是选择两个数字取 \(\gcd\)，剩下的数字分到另一个集合。
那么问题就变成了找出一对数字，它们的 \(\gcd\) 和剩下的数字的与做差值最大化。
怎么，是不是感觉这个问题还是非常抽象。
于是又开始人类智慧了。
发现如果数字非常多，与值很有可能等于 \(0\)。
于是我们在二进制位上面考虑问题。
现在我们考虑让与值为 \(0\)。
我们把某一位为 \(0\) 的数字个数记下来，那么如果这一位只有 \(1\) 个为 \(0\) 的数字，那么这个数字肯定不能取。
如果这一位只有 \(2\) 个为 \(0\) 的数字。那么这两个数字不能同时取。
也就是说最多只会有 \(19\) 条限制。
那如果不同数字的个数超过了 \(20\) 就一定可以使其与值为 \(0\)。
我们预处理 \(al_i\) 表示所有数字中第 \(i\) 位为 0 的数字个数。
于是我们枚举最大公约数 \(d\)，考虑将它的倍数全部提出来，集合称为 \(bs\)，以外的数字集合称为 \(out\)。
我们处理 \(in_i\) 表示集合 \(bs\) 中第 \(i\) 位为 0 的数字个数。
我们通过每一位的 \(al-in\) 可以快速求出集合 \(out\) 的与值。
然后考虑集合 \(in\) 中选择两个数字，分类讨论：
- \(|bs|\) 小于等于 \(20\)：
我们暴力枚举两个数字。然后用前缀后缀与快速求出其他数字的与值（记得和\(out\)的与在做一遍 & 运算），然后判断是否有解，时间复杂度 \(O(20\times 20)\)。 - \(|bs|\) 大于 \(20\)：
那么与值一定为 0，还是一样暴力扫两个值（因为限制只有 20 个，所以复杂度是对的）。
那么这一题基本做完了。写起来当然爽了。
这一题的细节和易错点：
- 有一些位，所有数字这一位都是 \(1\)，那么将这些位加起来为 \(s\)，那么最大公约数就从 \(s+x+1\) 开始枚举。
- 本题有重复数字。可以先特判一下选两个重复数字的情况。后面的枚举也要记得考虑这种情况！！！！
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define maxn(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod = 998244353;
mt19937 gen(114514);
ll rp(ll a,ll b) {ll res=1%mod;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int V = (1<<20)-1;
void solve() {
int n, c, m = 0;
scanf("%d%d", &n, &c);
VI a(n);
for (auto &x : a) {
scanf("%d", &x);
maxn(m, x);
}
VI cnt(m + 1);
for (auto x : a) cnt[x]++;
VI suf(m + 2);
suf[m + 1] = V;
rep(i,1,m) suf[i] = cnt[i] ? i : V;
per(i,m,1) suf[i] &= suf[i + 1];
auto print = [&](const int &x, const int &y) {
puts("YES");
printf("2 %d %d\n", x, y);
cnt[x]--; cnt[y]--;
printf("%d", n - 2);
rep(i,1,m) while (cnt[i]--) printf(" %d", i);
puts("");
};
int pre = V;
rep(i,1,m) {
if (cnt[i] > 2) pre &= i;
if (cnt[i] >= 2 && i > (pre & suf[i + 1]) + c) {
print(i, i);
return ;
}
if (cnt[i]) pre &= i;
}
VI al(21);
int one = 0, two = 0;
rep(i,1,m) if (cnt[i]) {
rep(j,0,20) if (~i>>j&1) al[j] += cnt[i];
}
int s = 0;
rep(j,0,20) {
if (!al[j]) s |= 1 << j;
else if (al[j] == 1) {
one |= 1<<j;
} else if (al[j] == 2) {
two |= 1<<j;
}
}
rep(d,s + c + 1,m) {
VI bs, in(21);
for (int b = d; b <= m; b += d) {
if (cnt[b]) {
bs.pb(b);
rep(i,0,20) if (~b>>i&1) {
in[i] += cnt[b];
}
}
}
int out = 0;
rep(i,0,20) if (al[i] == in[i]) {
out |= 1 << i;
}
if (SZ(bs) <= 20) {
suf = bs; suf.pb(V);
per(i,SZ(bs)-1,0) suf[i] &= suf[i + 1];
int l = V;
rep(i,0,SZ(bs)-1) {
int mid = V;
if (cnt[bs[i]] > 1) mid &= bs[i];
rep(j,i+1,SZ(bs)-1) {
if (cnt[bs[j]] > 1) mid &= bs[j];
if ((l & mid & suf[j + 1] & out) + c < d) {
print(bs[i], bs[j]);
return ;
}
mid &= bs[j];
}
l &= bs[i];
}
} else {
rep(i,0,SZ(bs)-1) {
int vi = V^bs[i];
if (one & vi) break;
rep(j,i+1,SZ(bs)-1) {
int vj = V^bs[j];
if (one & vj) break;
if (vi & vj & two) break;
print(bs[i], bs[j]);
return ;
}
}
}
}
puts("NO");
}
int main() {
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}