T1_快去打瓦 题解
前置知识：a+b=(a⊕b)+2(a∧b)a+b=(a\oplus b)+2(a\land b)a+b=(a⊕b)+2(a∧b)
其中 ⊕\oplus⊕ 表示异或运算，∧\land∧ 表示 C++\tt{C++}C++ 里面的 &\&& 运算。
稍微说一下，a⊕ba\oplus ba⊕b 表示了二进制下 a+ba+ba+b 但是不考虑进位，不处理进位的结果，即不进位加。
然后 a∧ba\land ba∧b 又表示二进制下所有 a+ba+ba+b 会进位的位权和，把这个位权和乘 222 就是只处理进位得到的结果。
所以把这两个东西加在一起就是 a+ba+ba+b。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
然后对于本题我们有一个结论如下。
结论：a⊕b≤a+ba\oplus b\le a+ba⊕b≤a+b。
证明：
* ∵a+b=(a⊕b)+2(a∧b)\because a+b=(a\oplus b)+2(a\land b)∵a+b=(a⊕b)+2(a∧b)
* ∴a+b−(a⊕b)=2(a∧b)\therefore a+b-(a\oplus b)=2(a\land b)∴a+b−(a⊕b)=2(a∧b)
* ∵2(a∧b)≥0\because 2(a\land b)\ge 0∵2(a∧b)≥0
* ∴a+b−a⊕b≥0\therefore a+b-a\oplus b\ge 0∴a+b−a⊕b≥0
* ∴a+b≥a⊕b\therefore a+b\ge a\oplus b∴a+b≥a⊕b
* ∴a⊕b≤a+b\therefore a\oplus b\le a+b∴a⊕b≤a+b
证毕。
所以两个数的时候答案就是这两个数的和，同理，三个数的时候就是三个数的和，nnn 个数的时候就是 ∑a\sum a∑a。
时间复杂度：O(n)O(n)O(n)
