Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11867 - Politeness (この記事を編集する[管理者用])

Source

Regional Warmup Contest 2010 (2010-10-09) (blog)
UVa 11867

問題概要

10^12以下の非負整数nが与えられる.
連続する2つ以上の正の整数の和がxとなるようなものの数をf(x)と書く.
f(x)=nとなる最小のxをmod 1000000007で求める問題.そのようなxが存在しないならそれを指摘する.

解法

ちょっと考えると,xを素因数分解して
 x = 2^p2 * 3^p3 * 5^p5 * …
とすると,
 f(x) = -1 + (p3+1) * (p5+1) * (p7+1) * …
となることがわかる.
なので,
 n+1 = a*b*c*d*…
と積の形で現してやり
 3^(a-1) * 5^(b-1) * …
の最小値が答えとなる.
まず,n+1を完全に素因数分解した形から,大きい数字からaに割り当てて行く.
あとは,適当に2つを掛けて,まとめてやって,再帰的に探索していく.
そのとき,2つをまとめて,答えが大きくなる場合は枝を刈って良いことがわかるので,刈ると間に合う.
答えの大小比較は,doubleでもオーバーフローしちゃうので,logを取って比較する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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