コンテンツにスキップ

ShareOJ Programming Contest vol.1 C - Add to Multiples

サイト
ShareOJ
コンテスト
ShareOJ Programming Contest vol.1
問題
C - Add to Multiples(常設版)

はじめすべて 00 の長さ NN の数列 AA があります。「kk と整数 xx を選び、kk の倍数番目の要素すべてに xx を足す」という操作を NN 回以下行って、A=(X1,…,XN)A = (X_1, \dots, X_N) にする操作列を 1 つ答える問題です。ただし ∣x∣≤1018|x| \le 10^{18} でなければなりません。

テストケースは TT 個あり、NN の総和は 3×1053 \times 10^5 以下、∣Xi∣≤109|X_i| \le 10^9 です。

kk を選ぶ操作で変わるのは Ak,A2k,…A_k, A_{2k}, \dots なので、kk より小さい番号の要素は変わりません。そこで、i=1,2,…,Ni = 1, 2, \dots, N の順に AiA_i を合わせていきます。

ii を見る時点で、AiA_i を変える操作は ii の約数 k<ik < i を選んだものだけで、それらはすでに済んでいます。したがって、今の AiA_i と XiX_i の差 x=Xi−Aix = X_i - A_i を求めて、k=ik = i で xx を足せば Ai=XiA_i = X_i になります。このあとの操作では AiA_i は変わりません。

各 ii について操作は高々 1 回なので、操作は NN 回以下です。

ii のときに足す値を xix_i とすると、Xi=∑d∣ixdX_i = \sum_{d \mid i} x_d が成り立ちます。これをメビウスの反転公式で解くと、xi=∑d∣iμ(i/d)Xdx_i = \sum_{d \mid i} \mu(i / d) X_d となります。μ\mu の値は −1,0,1-1, 0, 1 のどれかなので、∣xi∣|x_i| は (ii の約数の個数)×109\times 10^9 以下です。3×1053 \times 10^5 以下の整数の約数は多くても 180180 個なので、∣xi∣≤1018|x_i| \le 10^{18} を十分に満たします。

k=ik = i で足すときに書き換える要素は ⌊N/i⌋\lfloor N / i \rfloor 個です。合計は ∑i=1NN/i=O(Nlog⁡N)\sum_{i=1}^{N} N / i = O(N \log N) になります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(1, N + 1):
k = A[i - 1]
if k == 0:
continue
ans.append((i, k))
for j in range(1, N // i + 1):
A[i * j - 1] -= k
print(len(ans))
for i, j in ans:
print(i, j)

A を「あと足す必要がある量」として持ち、操作のたびにそこから引いています。k は足す値 xx で、00 のときは操作を省いています。