本文共 1787 字，大约阅读时间需要 5 分钟。

D. Ehab the Xorcist

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given 2 integers uu and vv, find the shortest array such that  of its elements is uu, and the sum of its elements is vv.

Input

The only line contains 2 integers uu and vv (0≤u,v≤1018)(0≤u,v≤1018).

Output

If there's no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, nn, representing the length of the desired array. The next line should contain nn positive integers, the array itself. If there are multiple possible answers, print any.

Examples

input

Copy

2 4

output

Copy

23 1

input

Copy

1 3

output

Copy

31 1 1

input

Copy

8 5

output

Copy

-1

input

Copy

0 0

output

Copy

0

Note

In the first sample, 3⊕1=23⊕1=2 and 3+1=43+1=4. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

给你一个u和v，然后让你构造一个元素个数最小的数组，使得这些数字的异或和为u，前缀和为v。

异或又被称为不进位加法，，

+2*a&b；

这个式子可以这样理解， 只是计算出每一位不考虑进位时候的情况，可以+还是进位的，进位的时候肯定是a,b 当前位都是1，才会往前进位。而a&b 第i为1，说明第i位该往前进位，而乘2则是整体左移，就是往前进位。然后在加上刚才没考虑进位的情况。

这个题目不存在解的情况，就是u>v 的情况和u,v奇偶性不同的情况。前者是因为异或是不进位加法，所以肯定不会大于加法的值；后者是因为，如果某一位u,v不一致，则肯定是进位造成的，而最后一位肯定没有进位，所以要为1都为1，要为0，都为0。 对于u==v 的情况直接输出u 就行。

(这个大佬的思路太通俗易懂了，，很感谢)。。。

对于一般情况，

a⊕b=u

a+b=a⊕b+2⋅a&b =u+2.a&b==v

因为

所以 我们令 就行 答案就是[u,x,x]  第一个样例长度为2 是因为u⊕x=u+x  所以是[u+x,x]

#include 
   
    using namespace std;typedef long long ll;int main(){     ios::sync_with_stdio(false);     ll u,v;     cin>>u>>v;     if(u==v&&u==0)     {         puts("0");         return 0;     }     else if(u==v)     {         cout<<1<<" "<
    <
     
      v||((u&1)!=(v&1)))     {         puts("-1");         return 0;     }     ll x=(v-u)/2;     if((u^x)==(u+x))     {         cout<<2<
      
       <
       
        <<" "<
        
         <
        
       
      
     
   

 

转载地址：http://ltyzi.baihongyu.com/