题目地址
题解
方法一
对每一位统计这一位上有多少个1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
#define INF 2000000000 using namespace std; typedef unsigned long long ll; ll n; void (){ 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$是奇数的情况上异或即可。
近期评论