Goで競プロメモ | 約数カウント - Qiita

最近、競技プログラミングを始めたのですが、才能はなく、要領も悪く、解法を覚えるのも苦手でどうしようもない弱者なのだと思い知る日々です。それでも、強くなりたいので、よく出てきそうなアルゴリズムやデータ構造や細かい Tips など何でも、メモできることはして、少しずつ知識と経験を蓄えていきたいと思って書いています。 今回は「約数カウント」についてメモします。 「約数カウント」 何をやるか $1$ からある正の整数 $n$ までの整数のそれぞれについて、正の約数の個数を数え上げる。 どうやるか 長さ $n + 1$ の整数配列 $A$ を用意する。（つまり $n$ までのインデックスを持つ配列） $1$ から $n$ までの整数について、配列 $A$ 内でその整数の倍数をインデックスとする要素をインクリメントしていく。 計算量: $O(n \log n)$ 調和級数になるため。（@ganariy