Imp is in a magic forest, where xorangles grow (wut?)
image
A xorangle of order n is such a non-degenerate triangle, that lengths of its sides are integers not exceeding n, and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order n to get out of the forest.
Formally, for a given integer n you have to find the number of such triples (a, b, c), that:
1 ≤ a ≤ b ≤ c ≤ n;
-
, whereimageimage
denotes the bitwise xor of integers x and y.
(a, b, c) form a non-degenerate (with strictly positive area) triangle.
Input
The only line contains a single integer n (1 ≤ n ≤ 2500).
Output
Print the number of xorangles of order n.
Example
Input
6
Output
1
Input
10
Output
2
Note
The only xorangle in the first sample is (3, 5, 6).
题意：在1到n内取3个数a,b ,c满足以下有条件
条件1：1<=a<=b<=c<=n
条件2：abc=0;
条件3：构成三角形
思路：x与本身的异或为0，位运算满足交换律
#include<cstdio>
using namespace std;
int cherk(int a,int b,int c){
return a+b>c;
}
int main(){
int n;
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
int k=i^j;// i ^ i = 0;
if(k>=j&&k<=n){ //保证前两边<=第三边，小的话其实是重复的（位运算满足交换律）
ans+=cherk(i,j,k);
}
}
printf("%d\n",ans);
return 0;
}
