记录做题时遇到的一些结论,随时更新。
\[\]\(x+y=(x\ \& \ y) << 1 + x \oplus y\)
若 \(a \oplus b=\gcd(a,b)\),那么有 \(a-b=a \oplus b\)。
证明:
设 \(a>b\),
因为 \(a-b \leq a \oplus b\),则有 \(\gcd(a,b) \geq a-b\)。
那么设 \(\gcd(a,b) = c\),令 \(a=k_1c,b=k_2c\),则有
\[a-b=(k_1-k_2) \cdot c(k_1 \geq k_2) \]那么有 \(\gcd(a,b) \leq a-b\)。
综上,有 \(\gcd(a,b)=a-b\),即 \(a-b=a \oplus b\)。
标签:结论,geq,gcd,遇到,leq,oplus,刷题 From: https://www.cnblogs.com/baijian0212/p/jielun.html