Almost All Multiples
Contest: Codeforces Round 836 (Div. 2)
Difficulty rating: 1400
Tags: greedy, number theory

Given two integers $$$n$$$ and $$$x$$$, a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$ is called funny if $$$p_i$$$ is a multiple of $$$i$$$ for all $$$1 \leq i \leq n - 1$$$, $$$p_n = 1$$$, and $$$p_1 = x$$$.

Find the lexicographically minimal$$$^{\ddagger}$$$ funny permutation, or report that no such permutation exists.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of each of the integers from $$$1$$$ to $$$n$$$ exactly once.

$$$^{\ddagger}$$$ Let $$$a$$$ and $$$b$$$ be permutations of length $$$n$$$. Then $$$a$$$ is lexicographically smaller than $$$b$$$ if in the first position $$$i$$$ where $$$a$$$ and $$$b$$$ differ, $$$a_i < b_i$$$. A permutation is lexicographically minimal if it is lexicographically smaller than all other permutations.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$; $$$1 < x \leq n$$$).

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if the answer exists, output $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the lexicographically minimal funny permutation $$$p$$$. Otherwise, output $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the permutation $$$[3,2,1]$$$ satisfies all the conditions: $$$p_1=3$$$, $$$p_3=1$$$, and:

- $$$p_1=3$$$ is a multiple of $$$1$$$.
- $$$p_2=2$$$ is a multiple of $$$2$$$.

In the second test case, the permutation $$$[2,4,3,1]$$$ satisfies all the conditions: $$$p_1=2$$$, $$$p_4=1$$$, and:

- $$$p_1=2$$$ is a multiple of $$$1$$$.
- $$$p_2=4$$$ is a multiple of $$$2$$$.
- $$$p_3=3$$$ is a multiple of $$$3$$$.

We can show that these permutations are lexicographically minimal.

No such permutations exist in the third test case.

Example input:
3
3 3
4 2
5 4

Example output:
3 2 1 
2 4 3 1 
-1

Editorial:
We start by giving the answer for $$$n=12$$$, $$$k=2$$$: $$$$$$[\color{red}{2}, \color{red}{4}, 3, \color{red}{12}, 5, 6, 7, 8, 9, 10, 11, \color{red}{1}]$$$$$$ and for $$$n=12$$$, $$$k=3$$$: $$$$$$[\color{red}{3}, 2, \color{red}{6}, 4, 5, \color{red}{12}, 7, 8, 9, 10, 11, \color{red}{1}].$$$$$$
As you can see, the array is almost the identity permutation, with certain elements rotated to the left. In particular, these are the elements that you get when you find the longest sequence $$$a_i$$$ such that $$$x \mid a_1 \mid a_2 \mid \dots \mid n$$$ (recall $$$a \mid b$$$ means $$$a$$$ divides $$$b$$$). For example, $$$3 \mid 6 \mid 12$$$ and $$$2 \mid 4 \mid 12$$$. To find this longest sequence, you need to prime factorize $$$\frac{n}{x}$$$. The complexity is $$$\mathcal{O}(n \log n)$$$.
The main idea is intuitive, but the proof is rather long. We include it below.
The idea is to look at cycles in the permutation. Consider any cycle of length greater than $$$1$$$, say $$$c_1, c_2, \dots, c_k$$$ (that is, $$$p_{c_1}=c_2$$$, $$$p_{c_2}=c_3, \dots, p_{c_k}=c_1$$$). We claim that for at least one element $$$c_i$$$ of the cycle, $$$p_{c_i}$$$ is not a multiple of $$$c_i$$$.
In fact, we'll show a more general claim: for one element of the cycle $$$p_{c_i} < c_i$$$, which implies that $$$p_{c_i}$$$ cannot be a multiple of $$$c_i$$$. Indeed, let's sum $$$p_{c_i} - c_i$$$ over all elements of the cycle. This sum is $$$0$$$, because each element appears once before the $$$-$$$ sign and once afterwards. Since none of these equal $$$0$$$, it follows that at least one of these terms is negative (and at least one is positive). If $$$p_{c_i} - c_i < 0$$$, then $$$p_{c_i} < c_i$$$, as desired.
So in each cycle, we must have at least one element breaking the key claim in the problem. But this claim holds for all $$$1 \leq i \leq n-1$$$, so the only cycle we can have goes through $$$p_n$$$! Indeed, since $$$p_n=1$$$ and $$$p_1=x$$$, the cycle goes $$$n \to 1 \to x \to \dots \to n$$$. For all arrows except the first one, we $$$a \mid b$$$ to write $$$a \to b$$$, because only $$$p_n$$$ can break the condition. Since we want the permutation to be lexicographically minimal, we want the longest such chain.
So we should find the longest sequence of numbers from $$$x$$$ to $$$n$$$, such that each number divides the previous. If there are multiple such sequences, we need to pick the one that puts smaller numbers earlier, since we want smaller elements earlier on in the sequence. To do this, we can just find the prime factorization of $$$\frac{n}{x}$$$ (it is the longest, since the primes cannot be broken up into smaller factors), sort it, and cycle it.