思路与证明
关键变换
设 x 的二进制在 20 位内，令集合 S 为 x 中为 1 的位位置集合，C 为其补集（即 x 中为 0 的位，数量记为 m）。
对任意候选数 a，要让与任意另一个 a′ 有 a & a′=x，显然 a 在 S 上必须全为 1。于是可以写成
P3442.第2题-美丽数组
题目内容
小美有一个最喜欢的小于 220 的非负整数 x 。
我们称数组 a 是 美丽的 ，当且仅当其满是以下所有条件：
现在小美想让你帮他找到一个最长的美丽数组。如果存在多个最长的美丽数组，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
输入描述
每个测试文件均包含多组测试数据。一行输入一个整数 T(1≤T≤500) 代表数据组数，每组测试数据描述如下：
输入一行一个整数 x(0≤x<220) ，表示小美最喜欢的非负整数。
输出描述
对于每组测试数据，先输出一行一个整数 k(1≦k≦100)，表示最长的美丽数组的长度。可以证明在本题的数据范围内，最长的美丽数组的长度不会超过 100 。
接下来，在第二行输出 k 个不同整数 a1,a2,…,ak(0≦ai<220) ，表示你找到的最长美丽数组。
样例1
输入
2
1048575
1048573
输出
1
113514
2
1048573 1048575
说明
对于第二组测试数据，找到的最长美丽数组 a 为 {1048573,1048575} 。检查发现， 1048573<220，1048575<220 ，且 1048573 & 1048575=1048573 。可以证明，不存在长度大于 2 的美丽数组。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
