Codeforces -> 1567B - MEXor Mixup

 1567B - MEXor Mixup: https://codeforces.com/problemset/problem/1567/B

Discussion:

1) first we have to take xor every number from 0 to (n-1) ,it's to costly to do it with for loops ,instead we can use properties of xor which are :

Let's denote the XOR of numbers from 0 to n as $\text{XOR}(�)$. The formula is as follows:

$$\{\begin{array}{ll}�& \text{if }�\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}4)\\ 1& \text{if }�\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)\\ �+1& \text{if }�\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}4)\\ 0& \text{if }�\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)\end{array}$$

Here, $\equiv$ denotes congruence (modulus). This formula provides a quick way to find the XOR of all numbers from 0 to n based on the value of n modulo 4.

For example:

• If n = 5, then $\text{XOR}(5)=5$ because 5 is congruent to 1 modulo 4.
• If n = 8, then $\text{XOR}(8)=8+1=9$ because 8 is congruent to 0 modulo 4.

You can use this formula to find the XOR of all numbers from 0 to n efficiently.

Let's denote xor of all elements until (0 to a-1) as c2.Now,if c2 xor b !=a then answer will be a+1 else the answer will be a+2.because ,if the xor is equal to a then to make b we have to add extra two numbers .

Code:

https://codeforces.com/problemset/problem/1567/B

#include<bits/stdc++.h>

using namespace std;

#define  ll       long long

#define  lg        long long

#define  fi(i,L,R) for (ll i = L ; i <= R ; i++)

#define  fd(i,R,L) for (ll i = R ; i >= L ; i--)

#define  s1        string

#define  p_b       push_back

#define  st(n)     sort(a,a+n)

#define  rev       reverse(a,a+n)

#define  revs(j)   reverse((j).begin(),(j).end())

#define  srt(k)    sort((k).begin(),(k).end())

#define  suni      s.erase(unique(s.begin(),s.end()),s.end())

#define  vuni      v.erase(unique( v.begin(),v.end()),v.end())

#define  puni      v1.erase(unique(v1.begin(),v1.end()),v1.end())

#define  yo       cout<<"YES"<<endl

#define  no       cout<<"NO"<<endl

#define  M        1000000007

#define  pie       acos(-1.0)

#define  pp        endl 

#define  sz        200000

#define m_p        make_pair

typedef pair<int, int> pi;

ll give_meXor(ll x){

     if(x%4==0) return x;

     else if(x%4==1) return 1;

     else if(x%4==2) return (x+1);

     else return 0;

}

void Solve()

{

              

        

            ll i,j,k,c=0,flag=0,c1=0,c2=0;

            ll a,b ; cin >>a>>b;

            c2=a;

            

            c1=give_meXor(a-1);

            

           

            if(c1==b){

                cout<<c2<<pp;

                return;

            }

            if((b^c1)!=a){

                cout<<c2+1<<pp;

            }

            else{

                cout<<c2+2<<pp;

            }

            

           

         

 

}

int main()

{ 

    ios::sync_with_stdio(false);

        cin.tie(0);

        int tt=1;

      

        

        cin>>tt;

        while(tt--)

        {

 

             Solve();

        }

        return 0;

}