백준 25367 (C++) 너무 시시했다

최초 업로드: 2025-08-30 05:24:45

최근 수정 시간: 2025-08-30 05:25:12

카테고리: 백준

# [Gold II] 너무 시시했다

[문제 링크](https://www.acmicpc.net/problem/25367)

## 문제 설명

영욱이는 민성이에게 다음과 같은 문제를 냈다.

<blockquote>
음이 아닌 두 정수 x와 y에 대해서 a + b = x이고 a ^ b = y인 음이 아닌 두 정수의 순서쌍 (a, b)는 모두 몇 개일까? (단, ^는 bitwise xor이다.)
</blockquote>

민성이는 이 문제가 너무 시시했다. 그러니 여러분이 대신 풀어 주자. 한 문제만 푸는 건 너무 시시하니까, q 문제를 동시에 풀어서 그나마 흥을 돋워 보자.

## 입력

첫 번째 줄에 질문의 수 q가 주어진다.

두 번째 줄부터 (q + 1) 번째 줄까지 각 줄에 각 질문의 x와 y가 공백으로 구분되어 차례로 주어진다.

## 출력

각 질문에 대해 조건에 맞는 (a, b) 쌍의 개수를 구하여 한 줄에 하나씩 차례로 출력한다.

## 풀이
A+B = A^B + (A&B)<<1 이라는 식을 풀고, A&B 와 A^B 비트를 비교하며 경우의 수를 세주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x, y;

ll solve() {
 // x = A+B = A^B + (A&B)<<1
 // (A&B)<<1 = x-y
 if(y>x || (x-y)&1) return 0;

ll ret=1;
 ll tmp = x-y >> 1;
 while(tmp || y) {
 if(y&1) {
 if(tmp&1) return 0;
 ret<<=1;
 }
 tmp>>=1; y>>=1;
 }
 return ret;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 cin >> x >> y;
 cout << solve() << '\n';
 }
}
```