2019-1-29-C

Posted on |

Problem

统计$a, b \in [1, n] (a \leq b)$中，有多少个数对$(a, b)$满足$gcd(a, b) = a \bigoplus b$

Solution

来一波XCY的证明

如果$gcd(a, b) = a \oplus b​$，那么$a \oplus b = b - a​$

又$\because xor$有一个性质：

$|a - b| \leq a \oplus b \leq a + b$

$\therefore a \oplus b = b - a​$

所以我们只要找到所有$a \oplus b = b - a$的情况，那么我们再判断一下$gcd(a, b) = a \oplus b$即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
int main()
{
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
	int n = read();
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = i << 1 ; j <= n; j += i){
			if(j - i == (j ^ i)){
				++ans;
			}
		}
	printf("%d\n",ans);
	return 0;
}