Qiitaに投稿しました。 qiita.com

\(O(\sqrt N )\) で解きます。 問題 リンクはこちら 概要 $$ \sum _ {i=1} ^ {N} i \cdot \mathit{d}(i) $$ を求めなさい。 解法 公式editorialの \(O(N)\) 解法を高速化することを考えたいです。結局、 \(S[k] := \sum _ {i=1} ^ {k} i\) として $$ \sum _ …

公式解説が分かりづらかったので 問題 リンクはこちら 概要 $$ \sum _ {i=0} ^ {n-1} \sum _ {j=i+1} ^ n \mathrm{lcm}(A _ i, A _ j) $$ を求めなさい。 解法 以下、計算は素数mod上で行うため、何かで割る操作は逆元を掛けているものだと思ってください。 …