B. Magic Forest
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Imp is in a magic forest, where xorangles grow (wut?)

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;
  • , where  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.

Examples
input
Copy 
6
output 
1
input
Copy 
10
output 
2
Note

The only xorangle in the first sample is (3, 5, 6).


题意:寻找满足要求的方案数,满足如下要求

1.1<=a<b<c<=n

2.(a^b)^c==0

3.构成三角形,3 个两边和 

思路:

O(n^2)暴力

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define bug cout << "bug" << endl
#pragma comment(linker, "/STACK:102400000,102400000")


using namespace std;
typedef long long ll;

const int MAX_N=1e5+5;

int main(void){
    int n,ans=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
                int k=i^j;
                if(k>j&&k<=n&&k<i+j&&i<k+j&&j<i+k){
                        ans++;
//                    printf("%d %d %d\n",i,j,k);
                }
        }
    }
    printf("%d\n",ans);
}