(爆破済) 約数の個数のオーダーは?
こんにちは。先日のABC136のE問題の計算量の見積もりに失敗してレートを落としたganmodokixです。今回は約数の個数のオーダーについて考えてみました。
お知らせ:この記事は根本的な誤りが見つかったため爆破しました。熨斗袋さんありがとうございます (2019.9.21)
記事を拝見したのですが、log(f(N)) ∈ Ο(g(N)) ⇒ f(N) ∈ Ο(exp(g(N))) は一般には成り立たないと思います
— 熨斗袋 (@noshi91) September 21, 2019
例えば log(N³) ∈ Ο(logN) ですが N³ ∉ Ο(N) です