Almost All Multiples (Codeforces 1758C)
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: 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: 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$$$.

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.

Sample Inputs:
3
3 3
4 2
5 4

Sample Outputs:
3 2 1 
2 4 3 1 
-1

Solution (Python):
import collections
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)
mod = 998244353

def solve():
    (n, x) = LI()
    if n % x != 0:
        return -1
    ans = [i for i in range(1, n + 1)]
    p = ans[0] = x
    for i in range(x + 1, int(n * 0.5) + 1):
        if n % i == 0 and i % p == 0:
            ans[p - 1] = i
            p = i
    (ans[p - 1], ans[n - 1]) = (n, 1)
    return ' '.join(map(str, ans))

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import collections
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)
mod = 998244353

def solve():
    (n, x) = LI()
    if n % x != 0:
        return -1
    ans = [i for i in range(1, n + 1)]
    p = ans[0] = x
    for i in range(x + 1, n - 1):
        if n % i == 0 and i % p == 0:
            ans[p - 1] = i
            p = i
    (ans[p - 1], ans[n - 1]) = (n, 1)
    return ' '.join(map(str, ans))

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout

def solve(n, x):
    if n % x != 0:
        return -1
    d = {i: i for i in range(1, n + 1)}
    i = 1
    while i < n:
        if x > n:
            return -1
        d[i] = x
        i = x
        if x == n:
            break
        for j in range(2, 20000):
            if n % (x * j) == 0:
                x = x * j
                break
            if x * j > n:
                return -1
    d[n] = 1
    return ' '.join(map(str, d.values()))
for _ in range(int(stdin.readline().strip())):
    (n, x) = map(int, stdin.readline().strip().split())
    ans = solve(n, x)
    stdout.write(f'{ans}\n')