yukicoder No. 1233 割り切れない気持ち 解説

なんかどっかでみた

解法ローラーをします.

式変形->modがあるのでかなりきびしい
もうない

制約をよくみます

a_i<=2e5,意味ありげですね.

とりあえず,入力を受け取って以下のようにします.
b[i]=(aの中で値がiとなる要素の個数)
累積和で以下を取れるようにします.
s1[l~r] : b[l]+...+b[r]
s2[l~r] : b[l]*l+...+b[r]*r

for i=1 to 200000
  for j=i to 200000以上のどっか, j+=i
    res+=b[i]*(s2[j-i~j-1] - s1[j-i~j-1] * (j-i) )

で終わりです.

計算量

調和級数のアレで二重ループはnlogn,結果O(nlogn)

なんでこれでいいの?

f:id:MUGEN_1337:20200918230646p:plain
こういう例を考えます

a[5]=5で他の要素をmodとって総和を数えることを考えます.
この時,幅5でシフトしていって和をとっていくことを考えると上の式がしっくりいくと思います
[0, 4]のところの和をとります.i*b[i]の和をとればいいので4です
[5, 9]の所の和をとります10+7-3*5で2です.なんでかというと,いま見ている幅5~9は5で割ると商は1だから,modをとるとそれぞれ-5されるからです.

これを考慮すると調和級数がぴったりはまって気持ちがいいですね.

提出

yukicoder.me

かわいい

おまるぽるかかわいくない?