CF-49C普及+/提高
构造排列
⏱ 2.0s💾 256MB
📋 题目描述
构造一个 的全排列,使得这个排列的因数最小。对于一个排列,它的因数 满足条件:存在一个下标 以及排列在第 个位置上的数字 满足: 并且 。
📥 输入格式
一个正整数 (),表示要构造的排列的大小。
📤 输出格式
共有 个正整数,一个因数最小的排列,若有多组满足要求的数据,输出任意一组即可。
📝 样例 1
输入
2
输出
2 1
📝 样例 2
输入
3
输出
1 3 2
📚 来源
Problem:CF-49C
💡 题目讲解
1
理解题意
这里的"因数"是题目自己定义的,和数学里的因数不是一回事。
对于排列 , 是"因数" 的意思是:存在位置 ,下标 和它上面的数 都能被 整除。即 且 。
用 举例,假设排列是 "2 1 3"():
| 1 | 2 | ✓ | ||
| 2 | 1 | ✓ | ✗ | |
| 3 | 3 | ✓ | ✓ |
逐行看:
- :,任何数都能被 1 整除 → 永远是因数,躲不掉。
- :唯一可能的位置是 (下标是 2 的倍数),但 不是偶数 → 不是因数。
- :,,都能被 3 整除 → 是因数。
这个排列有 2 个因数 {}。
再看样例 "1 3 2":
- :,, → 不是
- :,, → 不是
只剩 {},只有 1 个因数——这就是最优答案。
💡 目标:让所有 都找不到符合条件的 。
1 / 5