(模板)Luogu3380-2B平衡树

Posted on 2019-01-29

Problem

传送门

一个长度为n的序列，支持一堆操作，大致操作如下：

1.k在区间的排名(由小到大)2.区间第k小；3.单点修改；4&5：k的在区间上的前驱/后继。

2019-1-29-C

Posted on 2019-01-29

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$

$gcd(a, b) = a \oplus b \\ \Rightarrow gcd~|~a, gcd~|~b \\ \Rightarrow gcd~|~(b - a) \\ \Rightarrow a \oplus b~|~(b - a) \\ \Rightarrow a \oplus b \leq (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

#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;
}