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; } };