题解 CF1110C 【Meaningless Operations】

2019-02-09 22:04:36


分类讨论。

  • 如果 $a\not=2^i-1$

找到 $a$ 的最高的是 $1$ 的位,设这一位为 $x$ 。

如果 $b$ 取一个 $1\sim x$ 位都与 $a$ 相反的数,此时 $a\oplus b=2^{x+1}-1$ , $a\&b=0$ ,所以 $\gcd(a\oplus b,a\&b)=2^{x+1}-1$ 。

容易发现这样是最大的。

  • 如果 $a=2^i-1$

此时 $a\&b=b$ , $a\oplus b=a-b$ 。

于是 $\gcd(a\oplus b,a\&b)=\gcd(a-b,b)=\gcd(a,b)$ 。(后面那一步不懂的请百度更相减损术)

所以 $b$ 取 $a$ 的最大真因子时 $\gcd(a\oplus b,a\&b)$ 最大。

代码见blog