题目详情题解（0）讨论（0）提交记录（0）

CF1945H.GCD is Greater

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在徒步旅行的傍晚，Kirill 和 Anton 决定从背包里拿出一个长度为 nn 的整数数组 aa 来玩一个游戏。规则如下：

  1. Kirill 从数组中选择 22 到 (n−2)(n-2) 个数字，并用红色圈出它们。
  2. Anton 用蓝色圈出剩下的所有数字。
  3. Kirill 计算所有红色数字的最大公约数（GCD）。
  4. Anton 计算所有蓝色数字的按位与（bitwise AND），并将数字 xx 加到结果上。
  5. 如果所有红色数字的 GCD 严格大于所有蓝色数字的按位与与数字 xx 的和，则 Kirill 获胜；否则，Anton 获胜。

请帮助 Kirill 战胜 Anton，或者判断是否不可能。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 tt（1≤t≤200001 \le t \le 20000）——表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 xx（4≤n≤4⋅1054 \le n \le 4 \cdot 10^5，0≤x≤4⋅1050 \le x \le 4 \cdot 10^5）——整数的数量和数字 xx。

第二行包含一个长度为 nn 的数组 aa（1≤ai≤4⋅1051 \le a_i \le 4 \cdot 10^5）。

保证所有测试用例中 nn 的总和不超过 4⋅1054 \cdot 10^5。还保证每个测试用例中 aia_i 的最大值的总和不超过 4⋅1054 \cdot 10^5。

输出格式

对于每个测试用例，如果可以满足条件，则第一行输出 "YES"。第二行输出 Kirill 选择的数字个数和这些数字（顺序任意，空格分隔）。第三行输出 Anton 选择的数字个数和这些数字。

否则，输出 "NO"。

你可以用任意大小写输出每个字母。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被接受为肯定答案。

输入输出样例

  • 输入#1

    8
4 1
4 3 1 8
4 1
4 5 8 4
5 0
1 1 1 1 1
5 2
31 63 127 63 31
4 1
1 3 3 3
8 3
4 3 4 1 2 2 5 3
4 2
1 4 3 6
8 48
31 61 37 15 53 26 61 12

    输出#1

    YES
2 4 8
2 3 1 
YES
2 4 4
2 5 8 
NO
YES
2 63 63
3 31 127 31
YES
2 3 3
2 1 3
YES
2 4 4
6 3 1 2 2 5 3
YES
2 3 6
2 1 4 
YES
2 61 61
6 31 37 15 53 26 12

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页