思路：构造

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> b(n);

    const int MAXN = 1000000;
    vector<int> vis(MAXN + 1, 0);

    int cnt = 0;
    // 本质就是对于每个值找到还未被使用的最小值即可
    for (int i = 0; i < n; ++i) {
        int r = (i + 1) - a[i] % (i + 1);
        for (int j = r; j <= MAXN; j += i + 1) {
            if (!vis[j]) {
                b[i] = j;
                vis[j] = 1;
                cnt += 1;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) cout << b[i] << " \n"[i + 1 == n];


    return 0;
}

java

string = input()
n = len(string)

res = 0
for i in range(n-3):
    if string[i:i+4] == 'tzzt':
        res += (i+1)*(n-i-3)

print(res)

python

n = int(input())
nums = list(map(int, input().split()))


def solve():
    res = []
    pre = set()
    for i, a in enumerate(nums):
        b = (i + 1) - a % (i + 1)
        
        if b < 1:
            b += i + 1
        while b in pre and b < 10 ** 9:
            b += (i + 1)
        res.append(b)
        pre.add(b)
    
    print(*res, sep = " ")

solve()

题目内容

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

你需要使得这个数组 $b$ 的每个元素值都在 $[1, 10^9]$ 之间，且所有元素各不相同。

此外，你还需要使得 $(a_i + b_i)\mod i = 0, (1\leq i\leq 10^9)$ 。

输入描述

第一行，一个整数 $n(1\leq n\leq 10^5)$ ，表示数组的长度。

第二行，$n$ 个数表示数组 $a$ 的 $n$ 个元素，第 $i$ 个元素 $a_i\in [1, 10^6]$

输出描述

一行，$n$ 个数表示构造出的数组 $b$ 。

样例

输入

5
1 2 3 4 5

输出

1 2 3 4 5