洛谷3908 异或之和

发表于 | 分类于 |
字数统计: 162 字

题目地址

题解

方法一

对每一位统计这一位上有多少个1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#define INF 2000000000
using namespace std;
typedef unsigned long long ll;
ll n;
void init(){
    cin >> n;
}
void solve(){
    ll t = n, ans = 0;
    for(ll c = 1; ; c <<= 1){
        ll cnt = c * ((t / c + 1) >> 1) + (t % c) * ((t / c + 1) & 1);
        if(cnt & 1) ans |= c;
        if(t > c) t -= c;
        else break;
    }
    cout << ans << endl;
}
int main(){
    init();
    solve();
    return 0;
}

方法二

两个相邻（从0,1开始）的数异或必然为1。所以统计一下即可。如果$n$是偶数只要在$n$是奇数的情况上异或即可。