1. Description
有 n 个格子，编号为 1 到 n，初始时第 i 个格子中的数字为 i。
依次对 x = 1, 2, …, n 操作：将编号为 x 的倍数的格子中的数字，按编号递增方向循环移动一格，最后一个格子中的数字移到 x 号格子。格子编号不变。
输入一个整数 n，满足 1 <= n <= 10$^5$。
输出一行 n 个数字，依次表示操作结束后 1 到 n 号格子中的数字。
2. Solution
模拟
Time complexity: O(nlogn)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n + 1);
iota(nums.begin(), nums.end(), 0);
for (int x = 1; x <= n / 2; ++x) {
int last = (n / x) * x;
int temp = nums[last];
for (int j = last; j > x; j -= x) {
nums[j] = nums[j - x];
}
nums[x] = temp;
}
for (int i = 1; i <= n; ++i) {
cout << nums[i] << (i == n ? '\n' : ' ');
}
return 0;
}
|