C - Add to Multiples

解説

$i < i'$ のとき、 $k = i'$ の操作は $k = i$ の操作に影響を及ぼさないことに着目します。
この考察により、 $i$ の昇順に $A_i$ の値を $X_i$ の値に貪欲に揃えるのが正当であることが分かります。

よって、以下のアルゴリズムが正当です。

• $k = 1, 2, \cdots, N$ の順に以下の処理を行う。
  • $A_k, A_{2k}, \cdots, A_{\lfloor N/k \rfloor k}$ に対し、 $x = X_k - A_k$ を加算する。

また、この加算回数は調和級数の和を考えることで $O(N \log N)$ 回に抑えられます。

計算量はテストケースごとに $O(N \log N)$ であり、これは本問題の制約下において十分高速です。
言語と実装方針によってはオーバーフローが発生する場合があるため、十分注意してください。

実装例 (Python3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def solve():
    N = int(input())
    X = [int(s) for s in input().split()]

    A = [0] * N
    answers = []

    for i in range(1, N + 1):
        diff = X[i - 1] - A[i - 1]
        answers.append((i, diff))
        for j in range(i - 1, N, i):
            A[j] += diff

    print(len(answers))
    for k, x in answers:
        print(k, x)

T = int(input())
for _ in range(T):
    solve()