1758C.md (2053B)
1 Source: https://codeforces.com/problemset/problem/1758/C 2 3 C. Almost All Multiples 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 Find the lexicographically minimal$^{\ddagger}$ funny permutation, or report that no such permutation exists. 24 25 $^{\dagger}$ A permutation of length $n$ is an array consisting of each of the integers from $1$ to $n$ exactly once. 26 27 $^{\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 \lt b_i$. A permutation is lexicographically minimal if it is lexicographically smaller than all other permutations. 28 29 Input 30 31 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. 32 33 The only line of each test case contains two integers $n$ and $x$ ($2 \leq n \leq 2 \cdot 10^5$; $1 \lt x \leq n$). 34 35 The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 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$. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 3 3 49 50 4 2 51 52 5 4 53 ``` 54 55 Output 56 57 ``` 58 3 2 1 59 2 4 3 1 60 -1 61 ``` 62 63 Note 64 65 In the first test case, the permutation $[3,2,1]$ satisfies all the conditions: $p_1=3$, $p_3=1$, and: 66 67 * $p_1=3$ is a multiple of $1$. 68 * $p_2=2$ is a multiple of $2$. 69 70 In the second test case, the permutation $[2,4,3,1]$ satisfies all the conditions: $p_1=2$, $p_4=1$, and: 71 72 * $p_1=2$ is a multiple of $1$. 73 * $p_2=4$ is a multiple of $2$. 74 * $p_3=3$ is a multiple of $3$. 75 76 We can show that these permutations are lexicographically minimal. 77 78 No such permutations exist in the third test case.