PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: helloLad
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise operations
PROBLEM:
Given an integer X (which is \leq 10^9), find integers a and b such that a\ \&\ b and a\oplus b are both positive and divisible by X.
EXPLANATION:
Suppose we only had the condition on bitwise AND, i.e, we want to find a and b such that their AND is positive and divisible by X.
A rather simple solution in this case would be to just take a=b=X, since X\ \&\ X = X for any X.
Unfortunately X\oplus X = 0, so the bitwise XOR isn’t positive.
One way to fix this, is to simply place a shifted copy of X alongside X, that is, 2^K \cdot X for some large enough K.
For example, consider X = 13, which is 1011 in binary.
Then, if you take a=X and b=X + 2^{10} \cdot X, you’ll get in binary:
Note that their bitwise AND is still exactly X (as long as K is large enough, 2^K\cdot X won’t conflict with the existing bits of X, and will just cancel out in the bitwise AND.
Further, their bitwise XOR is exactly 2^K\cdot X (since the X's will cancel out now), which is also a multiple of X.
The question now is, what should K be?
It should satisfy two constraints:
- K should be such that it doesn’t interfere with the existing bits of X.
- Notice that this is automatically satisfied when K is ‘large enough’, i.e, when 2^K \gt X.
- K should also satisfy X + 2^K \cdot X \leq 8\cdot 10^{18}, since that’s our upper bound on a and b.
One simple solution is to just choose K = 32 always.
Since X \leq 10^9, 2^{32} is certainly greater than every X, and you can verify that no value ever exceeds 8\cdot 10^{18}.
tl;dr choose a = X and b = X + 2^{32}\cdot X.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x = int(input())
print(x, x + (x << 31))