题目描述

难度分:$1400$

输入$T( \leq 10^4)$表示$T$组数据。

每组数据输入$m(1 \leq m \leq 2^{29})$。

输出如下方程组的任意一组正整数解$(a,b)$

• $a \oplus b = m$
• $a + b = 2m$

$a$和$b$不能超过$2^{32}$。
如果无解输出$-1$。

输入样例

6
2
5
10
6
18
36

输出样例

3 1
-1
13 7
-1
25 11
50 22

算法

打表找规律

新年第一天的题目就不会做，打表发现$m$为奇数的时候肯定无解。$m$为偶数时可以构造出一个解$a=\frac{m}{2},b=\frac{3m}{2}$，此时需要满足$a \oplus b=m$，不满足就无解。

复杂度复杂度

时间复杂度

只进行了几次位运算和四则运算，因此时间复杂度为$O(1)$。

空间复杂度

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

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int T, m;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &m);
        if(m&1) {
            puts("-1");
        }else {
            int a = m >> 1;
            int b = 2*m - a;
            if(a^b == m) printf("%d %d\n", a, b);
            else puts("-1");
        }
    }
    return 0;
}