A. Array Divisibility 详细题解

题目重述

给定 $n$，要求构造一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$（每个数 $\le 10^5$），使得对于每一个 $k = 1, 2, \dots, n$，所有下标为 $k$ 的倍数的元素之和能被 $k$ 整除。即：

$$\forall k \in [1, n],\quad \sum_{j: k \mid j} a_j \equiv 0 \pmod{k}. $$

需要输出任意一个满足条件的数组。

观察与构造

一个极其简单且有效的构造是：

$$a_i = i \quad \text{for } i = 1, 2, \dots, n.$$

下面证明这个数组满足所有条件。

对于任意固定的 $k$，所有下标是 $k$ 的倍数的位置为 $k, 2k, 3k, \dots, mk$，其中 $m = \lfloor n/k \rfloor$。这些位置上的元素值恰好是 $k, 2k, \dots, mk$。它们的和为：

$$S_k = k + 2k + \dots + mk = k \cdot (1 + 2 + \dots + m) = k \cdot \frac{m(m+1)}{2}. $$

显然 $S_k$ 是 $k$ 的整数倍，因此 $S_k \equiv 0 \pmod{k}$。条件得证。

为什么这样构造可行？

• 每个 $a_i = i$ 都是正数，且 $i \le n \le 100$，而题目要求每个元素 $\le 10^5$，显然满足。
• 对于每个 $k$，求和自动提出因子 $k$，所以整除性成立。
• 代码实现只需输出 $1, 2, \dots, n$ 即可。

其他可能的构造

除了 $a_i = i$，还可以取 $a_i = c \cdot i$（$c$ 为任意正整数），或者更一般地，取 $a_i = i \cdot t_i$，其中 $t_i$ 为任意整数，只要保证每个 $k$ 的倍数位置上的和仍能被 $k$ 整除。最简单且满足题目数值上限的就是 $a_i = i$。

复杂度分析

对于每个测试用例，输出 $n$ 个数，时间复杂度 $O(n)$，空间 $O(1)$。由于 $n \le 100$，$t \le 100$，总计算量极小。

示例验证

样例中 $n=3$，输出 1 2 3 是否满足？

• $k=1$：和 $1+2+3=6$ 被 $1$ 整除。
• $k=2$：下标 $2$ 的值为 $2$，$2$ 被 $2$ 整除。
• $k=3$：下标 $3$ 的值为 $3$，$3$ 被 $3$ 整除。
  符合条件。但样例输出为 4 22 18，说明有多种答案，$1,2,3$ 也是正确的。

总结

本题的核心在于发现 $a_i = i$ 的简单构造，利用倍数和的因子提取性质直接满足整除要求。这是 Codeforces 上一道典型的“构造题”，通常考察观察能力，而非复杂算法。