noshi91のメモ

データ構造のある風景

2022-07-05から1日間の記事一覧

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

概要 を満たす の正整数の約数の個数の最大値は 程度と思っておけば競プロの計算量の見積もりで便利そう。 実験 を の正の約数の個数として、 と定義し、 と の関係を見る。 つまり、 と見積もると実際 *1 にはその 倍から 倍程度に収まることになる。 例え…