题目内容

小红有一个长度为 $n$ 的数组 $a$ ，他想让你用这个数组 $a$ 来构造一个长度同样为 $n$ 的数组 $b$ 。

思路：构造

对于每个 $a_i$ ，令 $r_i = a_i \mod i$ ，所以 $b_i \mod i = i - r_i$ 。

所以考虑 $b_i$ ，就枚举从 $i-r_i$ 开始，$i\times 2-r_i, i\times 3-r_i,...$ ，最多枚举到 $10^6$ 即可。

时间复杂度：$O(10^6 \times \log n)$

cpp