2025.05.22-得物春招机考真题解析-第二题

📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 👉 笔试突围OJ

02. 魔法书页重排

问题描述

A先生是一位魔法师，他有一本古老的魔法书，书中有 $n$ 页，每页都刻有一个魔法符号。最初，第 $i$ 页上刻着数字 $i$。

现在A先生需要按照古老的仪式来重新排列这些魔法符号。仪式的规则是：按照从小到大的顺序，对于每个 $[1,n]$ 之间的整数 $x$，将所有页码为 $x$ 的倍数的页面上的魔法符号向右循环移动一位。

具体来说，如果有 $k$ 个页面的页码是 $x$ 的倍数，分别为 $p_1,p_2,\dots ,p_k$（按页码从小到大排列），那么这些页面上的魔法符号会按如下方式移动：$p_k$ 页的符号移动到 $p_1$ 页，$p_1$ 页的符号移动到 $p_2$ 页，以此类推。

请输出仪式完成后每页上的魔法符号是什么。

输入格式

第一行包含一个正整数 $n$（$1\le n\le 10^5$），表示魔法书的页数。

输出格式

第一行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 页上的魔法符号。

样例输入

5

8

样例输出

5 3 2 1 4

8 7 3 5 4 2 6 1

数据范围

• $1\le n\le 10^5$

样例	解释说明
样例1	初始状态：[1,2,3,4,5]。x=1时，所有页面循环右移：[5,1,2,3,4]。x=2时，页面2,4循环右移：[5,3,2,1,4]。x=3时，页面3循环右移：不变。x=4,5同理
样例2	按照相同规则进行多轮循环移动操作

题解

这道题的关键是理解"循环右移"的概念，以及如何高效地模拟这个过程。

算法思路：

1. 初始化数组 $A[i]=i$
2. 对于每个 $x$ 从 $1$ 到 $n$，找出所有 $x$ 的倍数位置
3. 将这些位置上的数值进行循环右移

具体实现：

• 对于每个 $x$，收集所有倍数位置：$x,2x,3x,\dots$
• 如果只有一个位置，则无需移动
• 否则，保存最后一个位置的值，然后从后往前依次移动

举例说明（$n=5$）：

• 初始：$[1,2,3,4,5]$
• $x=1$：位置 $[1,2,3,4,5]$ 循环右移 → $[5,1,2,3,4]$
• $x=2$：位置 $[2,4]$ 循环右移 → $[5,3,2,1,4]$
• $x=3,4,5$：只有一个位置，无需移动

时间复杂度分析：对于每个 $x$，需要遍历其所有倍数，总的时间复杂度为 $O(n\log n)$，因为 ${\sum }_{x=1}^n\lfloor \frac{n}{x}\rfloor =O(n\log n)$。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()n = int(input())
a = [0] + list(range(1, n + 1))  # 1-indexed数组for x in range(1, n + 1):pos = []  # 存储x的倍数位置for j in range(x, n + 1, x):pos.append(j)if len(pos) <= 1:continue# 循环右移：最后一个元素移到第一个位置last_val = a[pos[-1]]for i in range(len(pos) - 1, 0, -1):a[pos[i]] = a[pos[i - 1]]a[pos[0]] = last_val# 输出结果（去掉第0个元素）
print(' '.join(map(str, a[1:])))

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {a[i] = i;  // 初始化}for (int x = 1; x <= n; x++) {vector<int> pos;  // 存储x的倍数位置for (int j = x; j <= n; j += x) {pos.push_back(j);}if (pos.size() <= 1) continue;// 循环右移int last_val = a[pos.back()];for (int i = pos.size() - 1; i > 0; i--) {a[pos[i]] = a[pos[i - 1]];}a[pos[0]] = last_val;}for (int i = 1; i <= n; i++) {cout << a[i];if (i < n) cout << " ";}cout << "\n";return 0;
}

• Java

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(System.out);int n = Integer.parseInt(br.readLine());int[] a = new int[n + 1];// 初始化数组for (int i = 1; i <= n; i++) {a[i] = i;}for (int x = 1; x <= n; x++) {List<Integer> pos = new ArrayList<>();// 收集x的倍数位置for (int j = x; j <= n; j += x) {pos.add(j);}if (pos.size() <= 1) continue;// 循环右移操作int lastVal = a[pos.get(pos.size() - 1)];for (int i = pos.size() - 1; i > 0; i--) {a[pos.get(i)] = a[pos.get(i - 1)];}a[pos.get(0)] = lastVal;}for (int i = 1; i <= n; i++) {pw.print(a[i]);if (i < n) pw.print(" ");}pw.println();pw.close();br.close();}
}

---