[Solution] Permutation GCD CodeChef Solution

Problem

Chef is interested in the sum of GCDs of all prefixes of a permutation of the integers $\{1, 2, \ldots, N\}$.

Formally, for a permutation $P = [P_1, P_2, \ldots, P_N]$ of $\{1, 2, \ldots, N\}$, let us define a function $F_i = \gcd(A_1, A_2, A_3, \ldots, A_i)$. Chef is interested in the value of $F_1 + F_2 + \ldots + F_N$.

Now, Chef wants to find a permutation of $\{1, 2, \ldots, N\}$ which has the given sum equal to $X$. Please help Chef find one such permutation. In case there is no such permutation, print $-1$. In case of multiple answers, any of them will be accepted.

A permutation of $\{1, 2, \ldots, N\}$ is a sequence of numbers from $1$ to $N$ in which each number occurs exactly once.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of a single line containing two space separated integers $N$ and $X$ denoting the length of required permutation and the required sum of GCDs of all prefixes respectively.

Output Format

• If there is a valid permutation that satisfies the required condition, then:
  • In a single line, output $N$ space-separated integers denoting the required permutation permutation.
• If there is no permutation, print $-1$ in a single line.

Explanation:

Test case $1$: The only possible permutation has a sum of $1$, as required.

Test case $2$: The two permutations of length $2$ are:

• $[1, 2]$ with a value of $1 + 1 = 2$
• $[2, 1]$ with a value of $2 + 1 = 3$

None of them have a sum of $X = 1$, so we output $-1$.

Test case $3$: For $P = [2, 4, 3, 1]$, we have:

• $F_1 = 2$
• $F_2 = \gcd(2, 4) = 2$
• $F_3 = \gcd(2, 4, 3) = 1$
• $F_4 = \gcd(2, 4, 3, 1) = 1$

The sum of these values is $6$, as required.