Sắp xếp tuyển tập

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho số nguyên dương $n$ . Hãy tìm một hoán vị $p_{1}, p_{2}, \dots, p_{n}$ của các số $1, 2, \dots, n$ sao cho số lượng ước số xấu là nhỏ nhất có thể.

Một số nguyên dương $i$ được gọi là ước số xấu nếu tồn tại chỉ số $j$ ( $1 \leq j \leq n$ ) thoả mãn đồng thời hai điều kiện:

$j mod i = 0$
$p_{j} mod i = 0$

Lưu ý rằng $i = 1$ luôn là ước số xấu vì $1$ chia hết cho mọi số. Bạn cần xây dựng hoán vị $p$ sao cho tổng số ước số xấu là nhỏ nhất.

Nếu có nhiều hoán vị thoả mãn, in ra bất kỳ hoán vị nào.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ .

Dữ liệu ra

In ra $n$ số nguyên trên một dòng, cách nhau bởi dấu cách — hoán vị $p_{1}, p_{2}, \dots, p_{n}$ tìm được.

Ràng buộc

$1 \leq n \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
2	2 1	Với $p = (2, 1)$ : $gcd (1, 2) = 1$ , $gcd (2, 1) = 1$ . Chỉ có $i = 1$ là ước số xấu, tổng cộng $1$ ước số xấu.
3	2 3 1	Với $p = (2, 3, 1)$ : $gcd (1, 2) = gcd (2, 3) = gcd (3, 1) = 1$ . Chỉ có $i = 1$ là ước số xấu.
1	1	$n = 1$ , hoán vị duy nhất là $(1)$ và $i = 1$ là ước số xấu duy nhất.

Bình luận

Không có bình luận tại thời điểm này.