51Nod 2653 区间xor

目录

• 51Nod 2653 区间xor
  • 目录
  • 1. 题目描述
    • 1.1. Limit
    • 1.2. Problem Description
    • 1.3. Input
    • 1.4. Output
    • 1.5. Sample Input
    • 1.6. Sample Output
    • 1.7. Source
  • 2. 解读
  • 3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131,072 kB

1.2. Problem Description

给出区间$(a,b)$，$b \ge a$，求 $a\ xor\ (a + 1)\ xor\ (a + 2)\ \dots \ xor \ b$ 。

---

1.3. Input

输入2个数：$a$ $b$，中间用空格分隔$(1 \le a \le b \le 10^9)$

---

1.4. Output

输出一个答案

---

1.5. Sample Input

3 8

1.6. Sample Output

11

1.7. Source

51Nod 2653 区间xor

---

2. 解读

计算区间$[1,b]$的区间异或，即求 $1\ xor\ 2\ xor\ 3\ \dots \ xor \ b$ 有如下规律。

当 $n\%4==0$ 时，$f(n) = n$; 当 $n\%4==1$ 时，$f(n) = 1$; 当 $n\%4==2$ 时，$f(n) = n+1$; 当 $n\%4==3$ 时，$f(n) = 0$;

数学上可以证明这个结论，可以参考Mychael的博客园博客。 我们可以记住这个公式，或者通过如下归纳推导出。

$n$	$x$	$cal(1,x)$	$n$	$x$	$cal(1,x)$
1	1	1	1	2	3
2	5	1	2	6	7
3	9	1	3	10	11
4	13	1	4	14	15
$n$	$4n+1$	1	$n$	$4n+2$	$x+1$

$n$	$x$	$cal(1,x)$	$1$	$x$	$cal(1,x)$
1	3	0	1	4	4
2	7	0	2	8	8
3	11	0	3	12	12
4	15	0	4	16	16
$n$	$4n+3$	0	$n$	$4n$	$x$

定义区间异或运算为 $cal(a, b)$，又因为异或运算 $z = xor(x, y)$ 的逆运算还是异或运算 $y = xor(x, y)$。那么要通过 $cal(1,b)$ 求 $cal(a, b)$，只需再对$[1,a-1]$进行一次异或运算即可。

$$cal(a, b) = cal(1, a - 1) \ xor \ cal(1, b)$$

3. 代码

#include <iostream>
using namespace std;

#define DEBUG

long long seriesXor(long long m, long long n)
{
    long long ans = m;
    for (long long i = m + 1; i <= n; i++) {
        ans ^= i;
    }
    return ans;
}

long long calculate(int x)
{
    if (x % 4 == 0) {
        return x;
    } else if (x % 4 == 1) {
        return 1;
    } else if (x % 4 == 2) {
        return x + 1;
    } else if (x % 4 == 3) {
        return 0;
    } else {
        return 0;
    }
}

int main()
{
    // 输入
    int a, b, ans = 0;
    scanf("%d %d", &a, &b);
    // 计算
    ans = calculate(b) ^ calculate(a - 1);
    // 输出
    printf("%d\n", ans);
    return 0;
}

---

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。