かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC172 D - Sum of Divisors

ABC 典型 式変形 競技プログラミング 解説 数論

問題はこちら

問題概要

整数{X}に対し，正の約数の個数を{f(X)}とする．{\displaystyle\sum_{K=1}^{N}K×f(K)}を求めよ．

{1\leq N\leq 10^7}

思考の流れ


正の約数の個数は，素因数分解や約数を列挙することによって{O(\sqrt{N})}で求まる．{1}から{N}に対してこれを行うと{O(N\sqrt{N})}かかる．

{\downarrow}
実際に約数の分布をみてみる．横の数字が{K}で約数に〇をかいた．

f:id:kanpurin:20210226104023p:plain

この図を横ではなく縦に見ると，上に書かれた数ごとに〇がかかれている．
つまり，上に書かれた数の倍数の和{\displaystyle\sum_{A=1}^{N}\sum_{B=1}^{\left\lfloor\frac{N}{A}\right\rfloor}A×B}が答え．

これは2重ループでそのまま書いても{O(N\log N)}，等差数列の和の公式を用いると{O(N)}となる．

また，{\displaystyle\sum_{K=1}^{N}f\left(\left\lfloor\frac{N}{K}\right\rfloor\right)}を{O(\sqrt{N})}で求める手法を使えば高速に解ける．

計算方法は以下の記事に書いてる．

kanpurin.hatenablog.com

他にも，{f(K)=\sum_{m|K}1}であるから約数におけるゼータ変換を用いることで{O(N\log{\log{N}})}でも解ける．

参考：https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5

提出プログラム

https://atcoder.jp/contests/abc172/submissions/20489255 {O(N)}
https://atcoder.jp/contests/abc172/submissions/20489357 {O(\sqrt{N})}

感想

{N\leq 10^{12}}でも解ける．