OJ周赛三场——异或和

标签：周赛 xor OJ int 异或 给定 return

异或和  

问题描述

给定多个测试数据。给定一对l,r。请你求出l,l+1....r的异或和

(异或的运算为两个数在二进制意义下，对于每一位，若相等则为0，否则为1，例如3 xor 4,即 二进制 11 xor 100 = 111 ，结果为5）

 

输入 

给定一个整数T（1≤T≤10）

接下来T行，每行给定两个整数l,r。(1≤l≤r≤10^9)

输出

输出T行，每行表示l到r的异或和。

 

输入例子 1 

1
3 5
1 4

输出例子 1

2
4

提示

第一个样例 3 xor 4 xor 5 = 2 

1 xor 2 xor 3 xor 4 = 4

我们令S(x)为0到x的异或和。那么根据异或的性质题目转换成S(r) xor S(l-1)

一个很明显的规律，即相邻的一对偶数和奇数2x和2x+1，观察发现除了最低位不同之外其他都相同，所以异或为1，那么这样的两对4个数异或为0，表现为

(0xor1xor2xor3=0) ,(4xor5xor6xor7=0)..

那么就是一个周期性的变化。所以可以直接求S(x)

这题原来想着少点数据让java和python快点 ，并且也在测试的时候卡掉了暴力，可能评测机波动导致导致暴力也能过QAQ

 

#include<bits/stdc++.h>
using namespace std;

int xorsum(int x){
	if ((x+4)%4==3) return 0;
	 else return xorsum(x-1)^x;
}

void  solve(){
	int l,r;
	cin>>l>>r;
	cout<< (xorsum(r)^xorsum(l-1))<<'\n';
}

int main(){
	int T;cin>>T;
	while(T--) solve();
}

　　

标签：周赛,xor,OJ,int,异或,给定,return
From： https://www.cnblogs.com/hihopkc/p/16952945.html