# 14283: 【原4283】憨憨求和

### 题目描述

author: Unknown 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4283

## 样例输入

2
4
233


## 样例输出

1
327


## 数据规模

| 测试点 | 特性 | | ------ | ------------------------------------------------ | | 1 | $n\le 100$ | | 2~3 | $n\le 1000$ | | 4~6 | $n\le 10^6$ | | 7 | $n=19260817$ | |8~10| $n\le 2\times 10^7$|

## zqy2018's solution

/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4283.md
*/
#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, ans = 0;
int ans2 = 12440306;
void init(){
}
void solve(){
ans = 0;
if (n < 10000000){
ans = (n - 1) >> 1;
for (int i = 2; i + i <= n; ++i){
for (int j = i + i; j <= n; j += i) {
if ((j ^ (j - i)) == i)
++ans;
}
}
}else {
ans += ans2 + ((n - 1) >> 1);
for (int i = 2; i <= 5000000; ++i){
for (int j = ((10000000 / i) + 1) * i; j <= n; j += i) {
if ((j ^ (j - i)) == i)
++ans;
}
}
for (int i = 5000001; i + i <= n; ++i){
for (int j = i + i; j <= n; j += i) {
if ((j ^ (j - i)) == i)
++ans;
}
}
}
printf("%d\n", ans);
}
int main(){