T273978 小武的方程

int_R · 2022-09-12 20:53:48 · 个人记录

~~校内模拟赛提前一个小时交代码并AK祭~~

没事干就直接写 T4 题解吧

写得太烂了

为什么别人写的都是

则方程有解当且仅当 A|(B-A)=A。

只有我的这么奇怪

前置：

题意很简单设 $x \lor y=A,x+y=B$，给出 $A,B$，问是否有合法的非负整数解 $(x,y)$。 **首先我们要知道 $ x \lor y+x \land y=x+y $** ~~不太严谨的~~证明：（以下的“每一位”指的是二进制位）我们知道二进制数的每一位非 0 即 1 。对于两个二进制数的每一位而言按位或操作：这两个数中这一位有一个或两个为 1 ，这一位就为 1 。按位与操作：这两个数中这一位有两个为 1 ，这一位就为 1 。普通加法操作：这两个数中这一位有一个为 1 ，这一位就为 1 ；这两个数中这一位有两个为 1 ，这一位就为 2 。（暂时先不考虑进位）换句话说 **在求和时，按位或操作计算时有一个 1 的计算了一次，但有两个 1 的也只计算了一次，但是两个 1 的应该计算两次，所以再加上按位与即为两数之和。** （我表达能力有限，~~好像~~说的不是很清楚）由 $ x \lor y+x \land y=x+y

移项得 x \lor y=(x+y)-(x \land y)

代入得 x\land y=B-A

因为这三项满足等式关系，所以想要满足 x \lor y=A,x+y=B ,我们只需满足 x+y=B,x \land y=B-A 即可

现在，重点来了，如何检验是否合法

我们设 C=x \land y=B-A

如果把每个数的二进制看作是字符串，那么 C 每一个为 1 的位，x 和 y 的那一位都一定为 1； C 每一个为 0 的位，x 和 y 的那一位最多只能有一个数 (x 或者 y) 为 1 ,既然这样，我们可以将 x 当做 C 。

B-2C+2C=B

y$ 当做 $B-2C+C

我们再将 y 拆成 C 和 B-2C

如果 C 中的某一位为 1，那么 B-2C 中的那一二进制位不能为 1（如果那样,x \land y 就不等于 C 了，因为可能会涉及进位），也就是只有保证 (B-2C) \land C 为假，x \land y 才等于 C。

所以

**所以结束** 当$(\ !\ (\ (\ (x+y)-2(x \land y)\ )\land(x \land y)\ )\ )$ 时，有合法解 $\ \ !\ (\ (\ (x+y)-2(x \land y)\ )\land(x \land y)\ )

=!((B-2(B-A)) \land (B-A))

=!(2A-B) \land (B-A)

\boxed{!(2A-B) \land (B-A)}

#include<cstdio>
using namespace std;
long long T,a,b;
int main()
{
    freopen("solution.in","r",stdin);
    freopen("solution.out","w",stdout); 
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&a,&b);
        ((!((2*a-b)&(b-a)))&&(2*a-b)>0)?puts("Possible"):puts("Impossible");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T273978 小武的方程

写得太烂了

******END******

END