题目 | AND and SUM - 颢天笔记

AtCoder Beginner Contest 238

D - AND and SUM

https://atcoder.jp/contests/abc238/tasks/abc238_d

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400$ points

Problem Statement

Solve the following problem for $T$ test cases.

Given are non-negative integers $a$ and $s$ . Is there a pair of non-negative integers $(x, y)$ that satisfies both of the conditions below?
$x AND y = a$
$x + y = s$

Constraints

$1 \leq T \leq 10^{5}$
$0 \leq a, s < 2^{60}$
All values in input are integers.

Input

Input is given from Standard Input. The first line is in the following format:

$T$

Then, $T$ test cases follow. Each test case is in the following format:

$a$ $s$

Output

Print $T$ lines. The $i$ -th line $(1 \leq i \leq T)$ should contain Yes if, in the $i$ -th test case, there is a pair of non-negative integers $(x, y)$ that satisfies both of the conditions in the Problem Statement, and No otherwise.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as $(x, y) = (3, 5)$ satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No

我的笔记

本题纯思维题，需要两个结论：

$(x XOR y) AND (x AND y) = 0$
$x + y = 2 \times (x AND y) + (x XOR y)$

下面来推导一下这两个结论。

先看第一个结论： $(x XOR y) AND (x AND y) = 0$

用具体的数来说明更形象，不妨令：
$x = 00110100_{2}$
$y = 11011110_{2}$

那么：
$x AND y = 00010100_{2}$
$x XOR y = 11101010_{2}$

观察上面两数，用通俗的话来解释：
$x AND y$ 的第 $a$ 位为 $1$ 就是 $x$ 和 $y$ 两数的第 $a$ 位同时都为 $1$
$x XOR y$ 的第 $a$ 位为 $1$ 就是 $x$ 和 $y$ 两数的第 $a$ 位有一个为 $1$

因此这两个事件不可能同时发生，即不可能两个数的同一位既同时为 $1$ 又有一个为 $1$ ，所以第一个结论得证。

再看第二个结论： $x + y = 2 \times (x AND y) + (x XOR y)$

我们把 $x$ 和 $y$ 都为 $1$ 的那位单独提出来（对应加号前的数）：
$x = 00110100_{2} = 00010100_{2} + 00100000_{2}$
$y = 11011110_{2} = 00010100_{2} + 11001010_{2}$

再将 $x$ 和 $y$ 相加：
$\begin{aligned} x + y & = 00010100_{2} + 00100000_{2} + 00010100_{2} + 11001010_{2} \\ = 2 \times 00010100_{2} + 11101010_{2} \\ = 2 \times (x AND y) + (x XOR y) \end{aligned}$

至于为什么另外两个数加起来是 $x XOR y$ ，那是因为把同为 $1$ 的提出去了，剩下的都是同为 $0$ 或二者之一为 $1$ ，加起来当然就是 $x XOR y$ .

本题解法：

本题知道：
$x AND y = a$
$x + y = s$

由第二个结论可求出 $x XOR y = s - 2 \times a$

再使用第一个结论，若 $(s - 2 \times a) AND a = 0$ ，则符合题意，反之不符合。

还有一个大前提， $s - 2 \times a$ 要 $\geq 0$ ，否则就肯定不成立。

源码

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        long long a, s;
        cin >> a >> s;
        long long x = s - 2 * a;
        if (x >= 0 && !(x & a))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

题目 | AND and SUM