1000ms

Difficulty: 5

所属公司 : 京东

时间 :2023年8月26日

算法与标签>构造

会员或题库专享

请先，开通会员或购买题库京东机考编程题库，可解锁完整内容。

购买京东机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

思路：构造

对于每个 $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

题目内容

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