题目题解

题意分析

题目要求我们构造一个长度为 $n$ 的严格递增序列
$1 \le a_1 < a_2 < \dots < a_n \le 100$，
使得对于任意 $1 \le i < j \le n$，满足：

即每个位置的“元素值对下标取模”的结果两两不同。

思路推导

第一步：分析取模结果的范围

对于第 $i$ 个位置，$a_i \bmod i$ 的结果只能是 $0, 1, 2, \dots, i-1$ 中的某一个数。

第二步：利用“所有结果互不相同”的条件

• 当 $i = 1$ 时：$a_1 \bmod 1 = 0$（唯一结果）。
• 当 $i = 2$ 时：$a_2 \bmod 2$ 可以是 $0$ 或 $1$。
  但 $0$ 已经被 $i=1$ 占用，所以必须取 $1$。
• 当 $i = 3$ 时：$a_3 \bmod 3$ 可以是 $0,1,2$。
  但 $0$ 和 $1$ 已经被占用，所以必须取 $2$。
• 依此类推，我们可以得到：

即每个 $a_i$ 必须满足：

第三步：转化为方程

由同余关系，$a_i$ 可以写成：

其中 $k$ 是非负整数。

第四步：增加递增和范围限制

• 序列严格递增：$a_1 < a_2 < \dots < a_n$。
• 题目要求 $a_i \le 100$。
• 同时 $a_i \ge i$（因为 $a_i \bmod i = i-1$，若 $a_i < i$ 则 $a_i = i-1$，但此时 $a_i \bmod i = i-1$ 也成立，不过 $a_{i-1}$ 可能已经占用该值，需要进一步检查）。

为了简单且可行，我们可以取 $k = 1$，即：

这样：

• $a_i \bmod i = (2i - 1) \bmod i = i - 1$，满足条件。
• 序列为 $1, 3, 5, \dots, 2n - 1$，严格递增。
• 当 $n \le 50$ 时，$2n - 1 \le 99 \le 100$，满足范围限制。

第五步：验证可行性

• 所有 $a_i \bmod i = i - 1$，互不相同（因为 $i - 1$ 互不相同）。
• 序列递增且值在 $1$ 到 $100$ 之间。
• 构造简单，直接输出 $2i - 1$ 即可。

算法步骤

1. 读入 $t$ 组测试数据。
2. 对于每组数据，读入 $n$。
3. 输出 $n$ 个数：$1, 3, 5, \dots, 2n - 1$。

时间复杂度

每组数据 $O(n)$，总复杂度 $O(\sum n) \le O(2500)$，非常高效。

参考代码

#include<bits/stdc++.h>
using namespace std;

void solve() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cout << 2 * i - 1 << ' ';
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) solve();
  return 0;
}

总结

本题的核心是通过分析取模结果互不相同的约束，推出每个 $a_i$ 必须满足 $a_i \equiv i-1 \pmod{i}$，然后取最简单的解 $a_i = 2i - 1$，即可在给定范围内构造出合法序列。