H. GCD is Greater

本文主要是介绍H. GCD is Greater，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

H. GCD is Greater

题意

  给定一个长度为$n$的数组$a$，先手选择$[2,n-2]$个数并计算所选择数的gcd，后手选择剩下的数，并计算剩下所有的数按位与的结果，再加上给定的$x$，如果先手的结果大于后手，则先手赢，否则后手赢。找出先手必胜的方案，或输出先手不可能获胜。

分析

  首先贪心地想到，若想gcd大，选择的数的数量越小越好，即只选择两个数，因为再选择别的数gcd不会再增加，而不会让结果更优。
  再考虑到后手的计算过程为剩下的数按位与，那么考虑每一位的最终结果，统计每一位在数组中出现了多少次。对于每一位，此时有三种可能，令先手选择的两个数的下标为$x_1$，$x_2$

• $x_1$和$x_2$中有一个数在该位为1
• $x_1$和$x_2$在该位的值都是1
• $x_1$和$x_2$在该位的值都是0

对于上述三种情况，当该位为$1$的数量$-(x_1$和$x_2$在该位为$1$的数量$)=n-2$，则后手计算的结果中这一位必定是$1$，否则必定是$0$，那么我们可以找到这些特殊点，即该位为$1$的数量为$n$或$n-1$或$n-2$时，$a_i$在该位非$1$，那么当我们选或不选它们对结果是有影响的。该集合大小为$2log(max(a_i))$。然后考虑除了上述情况的其他情况，根据贪心想法，肯定是gcd越大越好，那么我们可以存下每个数以及其约数出现次数的和，然后从大到小枚举gcd的大小，暴力判断即可，只需要判断能取到的最大gcd即可，其他的必然不会比最大的更优。
  对于会影响按位与的数，固定一个有影响的数，然后枚举另一个数，再暴力判断是否符合条件即可，时间复杂度$O(n((log(max{a}_i){)}^2+log(max{a}_i)logV))$，$logV$为计算gcd的复杂度

AC代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> p[400010];
void init() {for (int i = 1; i <= 400000; i++) {for (int j = i; j <= 400000; j += i) {p[j].emplace_back(i);}}
}
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);
}
void Solve() {int n, x;cin >> n >> x;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}int maxx = *max_element(a.begin() + 1, a.end());int L = __lg(maxx);vector<int> cnt(L + 1);vector<int> cnt1(maxx + 1);vector<int> z;for (int i = 1; i <= n; i++) {for (int j = 0; j <= L; j++) {if (a[i] >> j & 1) {cnt[j]++;}}}vector<bool> vis(n + 1);for (int j = 0; j <= L; j++) {if (cnt[j] < n - 2) {continue;}for (int i = 1; i <= n; i++) {if (!(a[i] >> j & 1)) {z.emplace_back(i);vis[i] = true;}}}for (int i = 1; i <= n; i++) {if (!vis[i]) {int sz1 = p[a[i]].size();for (int j = 0; j < sz1; j++) {cnt1[p[a[i]][j]]++;}}}vector<int> q;for (int i = maxx; i >= 1; i--) {if (cnt1[i] < 2) {continue;}for (int j = 1; j <= n && q.size() < 2; j++) {if (a[j] % i == 0 && !vis[j]) {q.emplace_back(j);}}int g = gcd(a[q[0]], a[q[1]]);int sum = 0;for (int j = 0; j <= L; j++) {int num = 0;if (a[q[0]] >> j & 1) {num++;}if (a[q[1]] >> j & 1) {num++;}if (cnt[j] - num == n - 2) {sum |= (1 << j);}}if (sum + x < g) {cout << "YES\n";cout << "2 " << a[q[0]] << " " << a[q[1]] << '\n';cout << n - 2 << " ";for (int j = 1; j <= n; j++) {if (j != q[0] && j != q[1]) {cout << a[j] << " ";}}cout << '\n';return;}break;}sort(z.begin(), z.end());z.erase(unique(z.begin(), z.end()), z.end());int sz = z.size();for (int i = 0; i < sz; i++) {for (int j = 1; j <= n; j++) {if (z[i] == j) {continue;}int sum = 0;for (int k = 0; k <= L; k++) {int num = 0;if (a[j] >> k & 1) {num++;}if (a[z[i]] >> k & 1) {num++;}if (cnt[k] - num == n - 2) {sum |= (1 << k);}}int g = gcd(a[j], a[z[i]]);if (sum + x < g) {cout << "YES\n";cout << "2 " << a[j] << " " << a[z[i]] << '\n';cout << n - 2 << " ";for (int k = 1; k <= n; k++) {if (k != z[i] && k != j) {cout << a[k] << " ";}}cout << '\n';return;}}}cout << "NO\n";
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);init();int T;cin >> T;while (T--) {Solve();}return 0;
}

这篇关于H. GCD is Greater的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---