問題
①整数LとRが与えられる。
②このとき、LからRまでの間全ての数をXORした後の値を求める。
解き方
L,Rは4*10^9のため単純なシミュレーションでは解くことができない。
そのため、数学的解法、法則を見つける。
法則を見つけるために1からずっとXORをしたときの値を並べてみると、
整数nを4で割ったときの余りによって以下になることがわかる。
余り0 → n
余り1 → 1
余り2 → n XOR 1
余り3 → 0
最後に1からスタートしているわけではなくてLからスタートしなければならない。
これは1からRまで求めた答えから、1からL-1まで求めた答えを引く、つまりXORしてあげればよい。
コード
class EllysXors {
public:
long long f(long long n){
long long check=n%4;
if(check==0)return n;
if(check==1)return 1;
if(check==2)return n^1;
return 0;
}
long long getXor(long long L, long long R) {
return f(R)^f(L-1);
}
};
public:
long long f(long long n){
long long check=n%4;
if(check==0)return n;
if(check==1)return 1;
if(check==2)return n^1;
return 0;
}
long long getXor(long long L, long long R) {
return f(R)^f(L-1);
}
};