noshi91のメモ

データ構造のある風景

競プロにおける約数の個数の見積もり

概要

$n \leq N$ を満たす $n$ の正整数の約数の個数の最大値は $N ^ {1/ 3}$ 程度と思っておけば競プロの計算量の見積もりで便利そう。

実験

$d(n)$ を $n$ の正の約数の個数として、 $\displaystyle r = \frac{\max _ {1 \leq n \leq N} d(n)}{N ^ {1 / 3}}$ と定義し、 $N$ と $r$ の関係を見る。

つまり、 $N ^ {1 / 3}$ と見積もると実際 *1 にはその $0.1$ 倍から $3.5$ 倍程度に収まることになる。

例えば、 $n \leq 10 ^ {12}$ なら $n$ の約数の個数の $2$ 乗が $10 ^ {8}$ より小さいくらいになって $1$ sec に間に合いそうと分かる。

*1:競プロだと $N \leq 10 ^ {18}$ がほとんどだろうという仮定の下