ShareOJ Programming Contest vol.1 C - Add to Multiples
- サイト
- ShareOJ
- コンテスト
- ShareOJ Programming Contest vol.1
- 問題
- C - Add to Multiples(常設版)
はじめすべて の長さ の数列 があります。「 と整数 を選び、 の倍数番目の要素すべてに を足す」という操作を 回以下行って、 にする操作列を 1 つ答える問題です。ただし でなければなりません。
テストケースは 個あり、 の総和は 以下、 です。
小さい番号から決める
Section titled “小さい番号から決める”を選ぶ操作で変わるのは なので、 より小さい番号の要素は変わりません。そこで、 の順に を合わせていきます。
を見る時点で、 を変える操作は の約数 を選んだものだけで、それらはすでに済んでいます。したがって、今の と の差 を求めて、 で を足せば になります。このあとの操作では は変わりません。
各 について操作は高々 1 回なので、操作は 回以下です。
のときに足す値を とすると、 が成り立ちます。これをメビウスの反転公式で解くと、 となります。 の値は のどれかなので、 は ( の約数の個数) 以下です。 以下の整数の約数は多くても 個なので、 を十分に満たします。
で足すときに書き換える要素は 個です。合計は になります。
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 は足す値 で、 のときは操作を省いています。