「UOJ#350」新年的XOR - xor性质

Link: UOJ #350

简要题意

构造一个长度大于 1 的区间 [L,R] 使得区间中所有整数的异或和恰好为 n

UOJ #350

在动物行为学中,Alpha对应动物群体中等级最高的个体,简而言之,就是人赢,那么AlphaGo自然就是人赢狗了。

但是狗群中还有众多的SingleDog,平日里他们和AlphaGo和谐相处,忍受着酸臭味自得其乐的活下去。但在2月14日这天,当AlphaGo在SingleDog们最后的防线——朋友圈秀恩爱的时候,他们实在按耐不住,决定密谋用FFF团的黑暗力量,打败AlphaGo。

但是AlphaGo的智商很高,很快便拦截了SingleDog们传输消息的异或值。为了让AlphaGo相信,SingleDog们只是在数朋友圈里的狗粮数,你,勇敢无畏的跳蚤,决定编造一个弥天大谎。

AlphaGo截获的是一个整数 n ,你需要构造一个长度大于 1 的区间 [L,R] 使得区间中所有整数的异或和恰好为 n

输入格式

第一行输入一个整数 t 表示数据组数。

接下来 t 行每行一个整数 n

输出格式

每组数据输出两个空格隔开的整数 L,R ,表示你构造的区间。要求 1 \leq L < R \leq 10^{18}

输入保证存在这样的区间。

样例

input

1
2
3
4
3
0
4
12

output

1
2
3
8 67
97 100
87 90

限制与约定

qwq 表格就不打了, 详见原题

时间限制: 1\texttt{s}

空间限制: 256\texttt{MB}

下载

样例数据下载


题解

看到题目后就打了个表....

1
2
3
int n = read();
int Xor = 0;
up (i, 1, n) printf("[1, %d] -> xor = %d\n", i, Xor ^= i);

这里为了避免影响体验就放出了 1\to 20 的表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[1, 1] -> xor = 1
[1, 2] -> xor = 3
[1, 3] -> xor = 0
[1, 4] -> xor = 4
[1, 5] -> xor = 1
[1, 6] -> xor = 7
[1, 7] -> xor = 0
[1, 8] -> xor = 8
[1, 9] -> xor = 1
[1, 10] -> xor = 11
[1, 11] -> xor = 0
[1, 12] -> xor = 12
[1, 13] -> xor = 1
[1, 14] -> xor = 15
[1, 15] -> xor = 0
[1, 16] -> xor = 16
[1, 17] -> xor = 1
[1, 18] -> xor = 19
[1, 19] -> xor = 0
[1, 20] -> xor = 2

你会发现一个规律:

f(t) = 1\text{ xor }2\text{ xor }\cdots t , 对于一个 k\equiv 1\pmod 4 , 有:

\begin{align} f(t) & = 1 \\ f(t + 1) & = t + 2 \\ f(t + 2) & = 0 \\ f(t + 3) & = t + 3\end{align}

证明其实很简单: 注意到 f(q) = f(q - 1)\text{ xor } q 即可

接下来就只用构造 f(q)\in[0,3] f(q)\equiv 1\pmod 2 就好了

其实第一个式子直接搜就完事了, 第二个简单地构造就完了(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define int long long
signed main () {
// int n = read();
// int Xor = 0;
// up (i, 1, n) printf("[1, %d] -> xor = %d\n", i, Xor ^= i);
int T = read();
while (T --> 0) {
int n = read();
switch (n) {
case 0: puts("1 919");
if (0) case 1: puts("810 1919");
if (0) case 2: puts("3 1001");
if (0) case 3: puts("1 2");
}
if (n <= 3) continue;
switch (n % 4) {
case 0: printf("1 %lld\n", n);
if (0) case 1: printf("%lld %lld\n", n - 3, n - 1);
if (0) case 2: printf("%lld %lld\n", n - 4, n);
if (0) case 3: printf("1 %lld\n", n - 1);
}
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!