文章目录
1. 题目描述
1.1. Limit
Time Limit: 1000 ms
Memory Limit: 131,072 kB
1.2. Problem Description
给出区间 (a,b), b≥a,求 a xor (a+1) xor (a+2) … xor b 。
1.3. Input
输入2个数: a b,中间用空格分隔 (1≤a≤b≤109)
1.4. Output
输出一个答案
1.5. Sample Input
3 8
1.6. Sample Output
11
1.7. Source
2. 解读
计算区间 [1,b]的区间异或,即求 1 xor 2 xor 3 … 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,有问题欢迎通过邮箱交流。