XORSGT Editorial

PROBLEM LINK:

Practice
Contest

SETTER:

xenon_shivam

TESTER:

animesh194

EDITORIALIST:

mukul166

DIFFICULTY:

EASY

PREREQUISITES:

Xor Properties

PROBLEM:

Given L to R find the xor of L to R.

QUICK EXPLANATION:

Let say XOR (Y) = 1 ⊕ 2 ⊕ 3 …⊕ Y
If we can find the value of XOR ( R ) and XOR ( L-1 ) then we can easily find the required answer by doing XOR ( L-1 ) ^ XOR ( R ).

EXPLANATION:

As constraints are very big in this problem so we can’t run loop for finding XOR ( R ) or XOR ( L ).
Trick to find XOR ( X ):
Xor of any 4 consecutive number is always 0
if X%4 \equiv 0 \bmod 4 then XOR ( X ) = X
if X%4 \equiv 1 \bmod 4 then XOR ( X ) = 1
if X%4 \equiv 2 \bmod 4 then XOR ( X ) = X + 1
if X%4 \equiv 3 \bmod 4 then XOR ( X ) = 0
Now we have XOR ( L -1 ) and XOR ( R ) we can easily calculate ( L )^( L+1 )+( L+2 )+…( R ).

SOLUTIONS:

Tester's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll fun(ll x){
if(x==0)return 0;
ll n=x;
x%=4;
if(x==0)return n;
if(x==1)return 1;
if(x==2)return n+1;
if(x==3)return 0;
return 0;
}
void solve(){
ll l,r;
cin>>l>>r;
if(l==0 and r==0)cout<<0<<"\n";
else if(l==0)cout<<fun®<<"\n";
else cout<<(fun(l-1)^fun®)<<"\n";
}

bool imp=true;int main(){
ll t;
t=1;
if(imp)
cin>>t;
while(t–)
solve();
return 0;
}