Fraction Construction (Editorial)

Observation : Lucas's Theorem provides a simple condition for odd binomial coefficients.

By Lucas's Theorem, \binom{n}{k} \equiv 1 \pmod 2 if and only if there are no carries when adding $k$ and n-k in binary. This is equivalent to saying the bitwise AND operation k \text{ \& } (n-k) = 0, or more simply, k \text{ \& } n = k.

Let's evaluate the condition for small values of a_i, a_j \in \{1, 2, 3\}:

• \binom{1}{1} = 1 (Odd)

• \binom{2}{2} = 1 (Odd)

• \binom{2}{1} = 2 (Even)

• \binom{3}{3} = 1 (Odd)

• \binom{3}{2} = 3 (Odd)

• \binom{3}{1} = 3 (Odd)

Notice that if we only use the value $3$, any pair $(3,3)$ contributes to $f(a)$. However, if we introduce the value $1$ or $2$, we can "break" the pairs. Specifically, a value of $3$ forms an odd binomial coefficient with $1,2,$ and $3$. A value of $1$ only forms an odd coefficient with another $1$ or a $3$. A value of $2$ only forms an odd coefficient with another $2$ or a $3$. Crucially, a pair $(1,2)$ results in \binom{2}{1} = 2, which is even.

Construction: To get exactly $x$ pairs, we start with $s$ elements of value $3$, where \binom{s}{2} \ge x. This gives us \binom{s}{2} odd pairs. To reduce this count to exactly $x$, we need to remove \text{rem} = \binom{s}{2} - x pairs. We can convert $\text{rem}$ elements from $3$ to $1$, and convert $1$ element to $2$. Since $(1,2)$ is even, the single $2$ will not form an odd pair with any of the $\text{rem}$ elements that are $1$, effectively subtracting exactly $\text{rem}$ from the total count.

from collections import defaultdict as dd

def C(x): return (x*(x-1))//2

mp=dd(int)
for i in range(1,10**5):
    mp[(i*(i-1))//2]=i

def solve():
    x,y=map(int,input().split())
    if(y<=1):
        for i in range(1,int(2*(x**0.5))+2):
            if(C(i)==x):
                print(i)
                print(*([1]*i))
                return
    if(y==2):
        for c1 in range(1,10**5):
            t = x - C(c1)
            if(t >= 0 and mp[t]!=0):
                c2=mp[t]
                print(c1+c2)
                print(*([1]*c1+[2]*(c2)))
                return
    if(y>0):
        l,r=1,2*10**9
        s=r 
        while(l<=r):
            m=l+(r-l)//2
            if((m*(m-1))//2>=x):
                s=m
                r=m-1
            else:
                l=m+1
        rem=s*(s-1)//2-x 
        c1,c2,c3=0,0,0
        if(rem==0):
            c3=s
        else:
            c1=rem
            c2=1
            c3=s-c1-c2 
        print(int(c1+c2+c3))
        print(*([1]*int(c1)+[2]*int(c2)+[3]*int(c3)))
        return

for _ in range(int(input())):
    solve()