题解 P3908 【异或之和】

Treeloveswater · 2018-04-15 09:23:31 · 题解

乱逛的时候看到了这题
随手推了一下，就A了。
为啥要结论？我来说一种非常严谨的做法。 并且是O(1)的。
题目要求 1^2^...^n，我们强制使得n为奇数 ，就是说如果n是偶数，我们就让n=n+1,然后让答案最后再异或n即可。
我们现在考虑一个奇数A，它的二进制形式是：ABCD1
A-1一定是偶数，其形式一定是 ABCD0
也就是说 A^(A-1)=000001 所以我们发现，除了最右边那一位，其他位都是0！
也就是说，我们现在只需要统计有多少个奇数即可！ 那么就很简单了。代码如下。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int main(){
    ll ans=0;
    scanf("%lld",&n);
    if(!(n&1)) n++,ans=n;
    ll num=(n+1ll)/2ll;
    if(num&1) ans^=1;
    cout<<ans;
}