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

构造排列

⏱ 2.0s💾 256MB

📋 题目描述

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

📥 输入格式

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

📤 输出格式

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

📝 样例 1

输入
2
输出
2 1

📝 样例 2

输入
3
输出
1 3 2

📚 来源

💡 题目讲解

1

理解题意

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

对于排列 a1..ana_1..a_n,ii 是"因数" 的意思是:存在位置 jj,下标 jj 和它上面的数 aja_j 都能被 ii 整除。即 j mod i=0j \bmod i = 0 且 aj mod i=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
12✓j%2≠0j\%2 \neq 0j%3≠0j\%3 \neq 0
21✓a2%2≠0a_2\%2 \neq 0 ✗j%3≠0j\%3 \neq 0
33✓j%3≠0j\%3 \neq 0✓

逐行看:

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

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

再看样例 "1 3 2":

  • i=2i=2:j=2j=2,a2=3a_2=3,3%2≠03\%2 \neq 0 → 不是
  • i=3i=3:j=3j=3,a3=2a_3=2,2%3≠02\%3 \neq 0 → 不是

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

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

1 / 5