Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1927-65c79c93
この記事にトラックバックする(FC2ブログユーザー)

UVa 11960 - Divisor Game (この記事を編集する[管理者用])

Source

Huge Easy Contest II (2011-04-09) (blog)
UVa 11960

問題概要

正整数N (10^6以下) が与えられるので,N以下の正整数で最も約数の数が多いもののうち,最も大きな数を出力する問題.
テストケースの数が50000個以下.

解法

テストケースが多いので,最初に全部のケースに対して答えを求める.
最初に,全部の数の約数を1個にセットして,2の倍数に約数の数を1加える,3の倍数に約数の数を1加える,…とやる.
これは,計算時間量は O( N + N/2 + N/3 + … + N/N ) = O(N log N).
後は,下からなぞって,約数の数の最大値が更新された時に更新していく.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1927-65c79c93
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。