题目描述

难度分:$2100$

输入$T(\leq 10^4)$表示$T$组数据。每组数据输入$n$、$m(1 \leq m \lt n \leq 10^{18})$。

你需要把$n$变成$m$。有如下操作，至多执行$63$次：

选择一个数$x$，满足$0 \lt x \lt n$且$0 \lt n \oplus x \lt n$，然后把$n$变成$x$或者变成$n \oplus x$。

如果无法把$n$变成$m$，输出$-1$。否则，设操作次数为$k$，首先输出$k$，然后输出 $k+1$个数，第一个数是初始$n$，其余$k$个数是每次操作后的$n$。

注意：你无需最小化操作次数。

输入样例

3
7 3
4 2
481885160128643072 45035996273704960

输出样例

1
7 3
-1
3
481885160128643072 337769972052787200 49539595901075456 45035996273704960

算法

构造

分以下情况讨论：

1. 如果$m \lt n$且$m \oplus n \lt n$，一次操作就可以完成，直接取$x=m$。
2. 如果一次操作后能够得到$k$，那么$m$的二进制需要是$k$的子集，不然肯定无解。得到包含$m$的$k$之后，再操作一次把不一样的位消掉就可以得到$m$，因此在这种情况下两次操作就能达到目的。于是我们先构造$k=m$，然后考虑减小$n \oplus k$。让$k$包含$n$最高位的$1$，这样一定可以满足$n \oplus k \lt n$（消去$n$最高位的$1$能最大限度减小$n$），同时保证$k$也尽可能小，接下来判断$k \lt n$是否成立即可。

复杂度分析

时间复杂度

$highbit$操作获得$n$的最高位，时间复杂度为$O(1)$，后面的构造+判断也都是$O(1)$的。因此，算法的时间复杂度为$O(1)$。

空间复杂度

仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int t;
LL n, m;

LL highbit(LL x) {
    return x != (1ll<<62)? (1ull<<(63 - __builtin_clzll(x))): 1ll<<62;
}

void solve(LL n, LL m) {
    if((n ^ m) < n) {
        printf("1\n%lld %lld\n", n, m);
        return;
    }
    LL k = m | highbit(n);      // 让k有n最高位的1
    if(k < n && (n^k) < n) {
        if((m&k) != m) {
            k ^= n;
        }
        printf("2\n%lld %lld %lld\n", n, k, m);
    }else {
        puts("-1");
    }
}

int main() {
    scanf("%d", &t);
    for(int cases = 1; cases <= t; cases++) {
        scanf("%lld%lld", &n, &m);
        solve(n, m);
    }
    return 0;
}