[Solution] Permutation GCD solution codechef

Permutation GCD solution codechef – Chef is interested in the sum of GCDs of all prefixes of a permutation of the integers \{1, 2, \ldots, N\}.

Table of Contents

[Solution] Permutation GCD solution codechef

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.

Permutation GCD solution codechef

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 1000
  • 1 \leq X \leq 2\cdot N – 1
  • The sum of N over all test cases won’t exceed 3\cdot 10^5.

Sample 1:

Input

Output

4
1 1
2 1
4 6
3 5
1
-1
2 4 3 1
3 2 1

Permutation GCD solution codechef 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.

For Solution

Click Here

Leave a Comment