codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.