🐷大肚肚
CF-49C普及+/提高

构造排列

2.0s💾 256MB

📋 题目描述

构造一个 1n1 \sim n 的全排列,使得这个排列的因数最小。对于一个排列,它的因数 ii 满足条件:存在一个下标 jj 以及排列在第 jj 个位置上的数字 aja_j 满足: j mod i=0j \ \bmod \ i=0 并且 aj mod i=0a_j\ \bmod\ i=0

📥 输入格式

一个正整数 nn1n1051 \le n \le 10^5),表示要构造的排列的大小。

📤 输出格式

共有 nn 个正整数,一个因数最小的排列,若有多组满足要求的数据,输出任意一组即可。

📝 样例 1

输入
2
输出
2 1

📝 样例 2

输入
3
输出
1 3 2

📚 来源

💡 题目讲解

1

理解题意

这里的"因数"是题目自己定义的,和数学里的因数不是一回事

对于排列 a1..ana_1..a_nii 是"因数" 的意思是:存在位置 jj下标 jj 和它上面的数 aja_j 都能被 ii 整除。即 jmodi=0j \bmod i = 0ajmodi=0a_j \bmod i = 0

n=3n=3 举例,假设排列是 "2 1 3"a1=2,a2=1,a3=3a_1=2, a_2=1, a_3=3):

jjaja_ji=1i=1i=2i=2i=3i=3
12j%20j\%2 \neq 0j%30j\%3 \neq 0
21a2%20a_2\%2 \neq 0j%30j\%3 \neq 0
33j%30j\%3 \neq 0

逐行看:

  • i=1i=1j=1j=1,任何数都能被 1 整除 → i=1i=1 永远是因数,躲不掉。
  • i=2i=2:唯一可能的位置是 j=2j=2(下标是 2 的倍数),但 a2=1a_2=1 不是偶数 → i=2i=2 不是因数
  • i=3i=3j=3j=3a3=3a_3=3,都能被 3 整除 → i=3i=3 是因数

这个排列有 2 个因数 {1,31, 3}。

再看样例 "1 3 2"

  • i=2i=2j=2j=2a2=3a_2=33%203\%2 \neq 0 → 不是
  • i=3i=3j=3j=3a3=2a_3=22%302\%3 \neq 0 → 不是

只剩 {11},只有 1 个因数——这就是最优答案。

💡 目标:让所有 i2i \ge 2 都找不到符合条件的 jj

1 / 5