Or Sum#12338

Or Sum (Editoryal)

Problem Author:	Khoi Le
Prepared by:	Khoi Le
Edited by:	Hasan Saleh (MathModel)

Observation : It's optimal to pick the integers with highest bits on

Notice for $k \geq 2$ k \ge 2 we can pick two integers $x, y$ such that

bin (x) \cup bin (y) = ⌊ l o g_{2} (n)⌋ 1111...1 = 2^{⌊ l o g_{2} (n)⌋ + 1} - 1

\text{bin}(x) \cup \text{bin}(y)=\underbrace{1111...1}_{\lfloor \log_2(n) \rfloor}=2^{\lfloor \log_2(n) \rfloor+1}-1

We shall prove by construction :

Let $x = 2^{⌊ l o g_{2} (n)⌋} = 10000...0$ x=2^{\lfloor \log_2(n) \rfloor}=10000...0 and $y = x - 1$ y=x-1 i.e. $0111111...11$ then

x ∣ y = ⌊ l o g_{2} (n)⌋ 1111...1 = 2^{⌊ l o g_{2} (n)⌋ + 1} - 1

x|y=\underbrace{1111...1}_{\lfloor \log_2(n) \rfloor}=2^{\lfloor \log_2(n) \rfloor+1}-1

If $k = 1$ k=1 then the answer is $n$ .

def solve(): 
    n,k=map(int,input().split())
    if(k==1):
       print(n)
    else:
       print((1 << n.bit_length())-1)
for _ in range(int(input())):
    solve()

Python