Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2123 - Divisor Function (この記事を編集する[管理者用])

Source

ICPC OB/OG会 冬合宿2008: コンテスト2
Aizu 2123

問題概要

Nの正の約数の和をS(N)と書くことにする.1以上k以下のnに対して
 S(n)/n
の最大値を求める問題.
kは10^15以下.

解法

 S(n)/n
が以前までの数字のどれよりも大きくなるnを最初に列挙しておく(この集合をTとする).後はなぞれば答えれる.
で,S(n)/nが大きくなるのは,小さい素数で素因数分解できるもの.
なので,今まで計算したTの要素に1つ小さな素数を掛けて,今までのS(n)/nの値のどれよりも大きく,一番小さい数字をTに加える,ということを繰り返す.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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