SRM 543 250pt : EllysXors

問題概要

[L,R](1<=L<=R<4*10^12)に含まれるすべての数のxorをとったものを求める問題。

解法

以前1~Nまでのxorがどうなるか調べたことがあって、それを思い出すだけで良かった。
1~Nまでの累積xorはmod 4で周期性が現れる。2*n ^ (2*n+1) = 1になって、その1を打ち消すのにさらに2つかかるという理屈。

acceptされたコード

typedef long long int64;

struct EllysXors {

	int64 getXor(int64 L, int64 R) {
		int64 r = sub(R), l = sub(L-1);
		return r ^ l;
	}

	int64 sub(int64 n){
		if(n == 0){
			return 0;
		}
		if(n%4 == 0){
			return n;
		}
		if(n%4 == 1){
			return 1;
		}
		if(n%4 == 2){
			return n+1;
		}
		return 0;
	}

};