# PRIME_XOR - EDITORIAL

Setter: Mithil Shah

Testers: Nishank Suresh and Abhinav Sharma

Editorialist: Mithil Shah

1519

None

# PROBLEM

For 3 distinct prime integers A, B, and C (1 \lt A,B,C \lt 2^{30}), we define positive integers X, Y, and Z as:

X = A\oplus B, Y = B\oplus C, and Z = C\oplus A, where \oplus denotes the bitwise XOR operation.

Given only two integers X and Y and the fact that at least one integer amongst X, Y, and Z is odd, find the values of A, B, and C.

# EXPLANATION

### First Observation:

If we have X and Y then we can get Z by taking bitwise XOR of the X and Y.

Proof

X=A\oplus B, Y=B\oplus C and X\oplus Y=(A\oplus B)\oplus (B\oplus C)=A\oplus C=Z.

### Second Observation:

It is given that at least one integer amongst X, Y, and Z is odd, this implies one of the numbers from A, B, and C must be even as bitwise XOR of even and odd number gives odd.

The only even prime number that exists is 2, hence we have concluded one number out of A, B, and C.

To obtain the remaining two numbers from A, B, and C, we can take bitwise XOR of 2 and two odd numbers out of X, Y, and Z.

Hence, we arrive at the values of all A, B, and C.

# TIME COMPLEXITY

The time complexity is O(1) per testcase.

# SOLUTIONS

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < n; i++)
#define endl '\n'
#define fastio                    \
ios_base::sync_with_stdio(0); \
cin.tie(0);                   \
cout.tie(0);
void tosolve()
{
vi a;
int b[3];
cin >> b[0] >> b[1];
b[2]=b[0]^b[1];
a.pb(2);
if (b[0] % 2 == 0)
{
a.pb(2^b[1]);
a.pb(2^b[2]);
}
else if (b[1] % 2 == 0)
{
a.pb(2^b[0]);
a.pb(2^b[2]);
}
else if (b[2] % 2 == 0)
{
a.pb(2^b[0]);
a.pb(2^b[1]);
}
sort(a.begin(), a.end());
rep(i,3)
{
if(i==2) cout<<a[i]<<endl;
else cout<<a[i]<<" ";
}
return;
}

int32_t main()
{
fastio;
int t;
cin>>t;
while(t--)
{
tosolve();
}
return 0;
}
``````
Tester-1's Solution
``````for _ in range(int(input())):
x, y = map(int, input().split())
ans = [2]
if x%2 == 1:
ans.append(x^2)
if y%2 == 1:
ans.append(y^2)
else:
ans.append(y^ans[1])
else:
ans.append(y^2)
ans.append(ans[1]^x)
print(*sorted(ans))
``````
Tester-2's Solution
``````#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back

int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;

using ii = pair<ll,ll>;

bool chk_pr(int x){
for(int i=2; i*i<=x; i++) if(x%i==0) return 0;
return 1;
}
vector<int> pr;
void pre(){
rep_a(i,2,40005){
if(chk_pr(i)) pr.pb(i);
}
}

bool fun(int x){
for(auto h:pr){
if(h*h>x) return 1;
if(x%h==0) return 0;
}

return 1;
}

void solve(){

int z = x^y;

int a[3];
a[0]=a[1]=a[2]=2;

if(x&1) a[0] = x^2;
if(y&1) a[1] = y^2;
if(z&1) a[2] = z^2;

sort(a,a+3);

assert(a[0]!=a[1] && a[1]!=a[2]);

assert(fun(a[0]) && fun(a[1]) && fun(a[2]));

cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<'\n';
}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;

int t = 1;
pre();

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);
//assert(sum_n<=3e5);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';

cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
``````

Feel free to share your approach. Suggestions are welcomed.

1 Like

The main thing here was that if atleast one number among x,y,z is odd then it implies that the least significant bit of either A or B or C must be 0 or simply say any one among A,B,C will be even. Since we are given that A,B,C should be prime therefore we got our one value that is 2 because 2 is the only even prime number. so say if our A was 2 then our B will be 2^X and C will be B^Y .and if both B and C are odd then this A,B,C is our answer. If our B was 2 then our A will be 2^X and C will be 2^Y and if A and B are both odd then this will be our answer . If our C was 2 then B will be Y^2 and A will be X^B and if B and A are odd then this will be our answer.

2 Likes

anyone please explain this problem in terms of bits

what should a,b,c for x=1 and y=2??

1 Like

my solution is giving 1 2 3. But 1 is not prime. I think constraints are wrong in problem

exactly i wasted time on this test-case and setterâ€™s code gave 1,2,3 as output.

In the problem, it is guaranteed that a unique answer exists, so such combination x=1 and y=2 does not occur in test cases as there is no unique answer for such x and y.

It is given that at least one integer amongst X, Y and Z is odd that means the LSB of at least one integer (amongst X, Y and Z) should be set bit (1).
in XOR opration
1 xor 1 = 0
0 xor 0 = 0
1 xor 0 = 1
0 xor 1 = 1
that implies that amongst a,b,c at least one integerâ€™s LSB should equal to 0
Inshot we need one even number for the given condition
and in question we given that the number a,b,c is prime
2 is the only even prime number
so now we can say that A should be 2 alway
let
x = 2^b
y = b^c
z = c^2
by the property of xor if we take xor of any odd number (bcoz 2 is the only even prime) with 2 ans will be odd number
if x is odd that means it is a vaild ans so take xor of x with 2 will give you the ans and so on.

yaaa 1 thing i forgot to mention is that
if x = a^b
and y = b^c
than x^y = a^c
for example
011
^100

111
then
111
^011

100
bcoz x^x = 0
here x is any integer.

1 Like