首页 > 其他分享 >CF 1790E. Vlad and a Pair of Numbers_Codeforces Round #847 (Div. 3)

CF 1790E. Vlad and a Pair of Numbers_Codeforces Round #847 (Div. 3)

时间:2023-01-28 09:34:05浏览次数:54  
标签:847 Vlad int scanf 1790E Codeforces bigoplus printf

给出整数x,求一对整数(a, b),满足:
\(a\bigoplus b=x\), \(\frac{a+b}{2}=x\)(\(\frac{a+b}{2}\)不四舍五入,也就是\(2\mid a+b\))
如果不存在这样的(a, b)输出-1
分析:

  • 如果x的最后一位是1,根据异或,a与b中最后一位分别为0,1,这样a+b最后一位是1,不被2整除,所以这种情况无解
  • 如果x中有连续的两个1,如0110
    • 根据\(a\bigoplus b=x\),a与b的第3位(从右往左第3位)分别为1,0;第2位同理,只能分别为1,0
    • 由于\(a+b=2x\),所以\(a+b\)的第3位和第4位应为1 1
    • 上述两种情况无法同时成立。所以x中不能出现连续的两个1,即(x>>1)&1应为0
  • 上述两种无解情况之外的情况就有解了,\(a=(x>>1), b=x\mid (x>>1)\)

结论:\(a\bigoplus b=x\), \(a+b=2x\) 想要成立,需要满足x&1=0,(x>>1)&x=0,其中一对整数a, b分别为\(x>>1, x|(x>>1)\)

#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int x;
	scanf("%d", &x);
	if(x%2==1){
		printf("-1\n");
	}else{
		if(x&(x>>1)){
			printf("-1\n");
		}else{
			printf("%d %d\n", x>>1, x|(x>>1));
		}
	}
}
int main(void)
{
	int T=1;
	scanf("%d", &T);
	while(T--)solve();
	return 0;
} 

标签:847,Vlad,int,scanf,1790E,Codeforces,bigoplus,printf
From: https://www.cnblogs.com/JustACommonMan/p/17069659.html

相关文章