题目描述

小C喜欢异或，他有一天突然在思考一个问题。

他构造了一个无穷多的数组a ，其中第一个元素a1=1，第二个元素a2=1^2，...，第i个元素ai= 1^2^...^i...

其中"^"表示二进制异或运算。 他想知道在1~n的所有整数中，有多少整数不在数组a中。

输入格式

一行一个整数n。 输出格式

输出一个数表示答案。

输入样例

2

输出样例

1

说明：

a1=1,a2=3,a3=0,a4=4...

1<=n<=10^18

代码:

#include <bits/stdc++.h>
using namespace std;
long long n,a[4];
long long yh(long long x,long long y){
	return x ^ y;
}
int main(){
	cin>>n;
	a[1]=0;
	a[2]=a[3]=a[4]=1;
	if(n<=4) cout<<a[n];
	else{
		for(int i=1;i<=4;i++) a[i]+=2*((n-1)/4);
		if(n%4==0) cout<<a[4];
		else cout<<a[n%4];
	}
	return 0;
}