[Daimayuan] 简单的异或问题（C++，数学）

有一组整数 {0,1,2,…,2m−1}\\{0,1,2,…,2_{m−1}\\}{0,1,2,…,2m−1​}, 请从中选出 $k$ 个数，使得这 $k$ 个数的异或和为 $n$, 请输出最大的满足条件的 $k$。

输入格式

两个数 $n$ 和 $m$, 其中 $0\le n\le 2m-1,1\le m\le 60$。

输出格式

输出最大的满足条件的 $k$。

样例输入

2 2

样例输出

3

样例解释

对于样例，我们可以选择 $0,1,3$。

解题思路

首先介绍一下异或和：

异或操作：同则为假，不同为真

1^0=1
0^1=1
0^0=0
1^1=0

给定两个数，这里以$8$和$4$为例，其异或和

0000 1000
0000 0100
---------
0000 1100

接下来是解题思路：

这里先列出来一部分二进制格式的数字

0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15

然后我们可以发现：任意数量大于$1$的$0$与相同数量的$1$作异或操作，无论顺序，结果均为$0$

再进一步看到：当$m>1$时，$0$~2m−12^m-12m−1之内的所有数的异或和为$0$

那么当$m>1$时，我们想得到任意数字n∈[0,2m−1]n \\in [0, 2^m-1]n∈[0,2m−1]且$n\ne 0$，只需要从异或和中去掉$n$即可

当$m=1$时，我们进行特殊判定即可

AC代码如下

#include <iostream>
using namespace std;int main() {long long n, m;cin >> n >> m;if (m == 1) {if (n) cout << 2 << endl;else cout << 1 << endl;}else {if (!n) cout << (1LL << m) << endl;else cout << ((1LL << m) - 1) << endl;}return 0;
}

华夏名砚网