Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12546 - LCM Pair Sum (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12546

問題概要

nが素因数分解された形で与えられるので,
 f(n) = sum[1 ≤ p ≤ q ≤ n, LCM(p,q)=n] (p+q)
の値を mod 1000000007 で求める問題.
nの素因数はそれぞれ1000以下で,含まれる素因数の種類は15種類以下,各素因数の数は50以下.

解法

p ≤ qという大小関係を無視して,(p, q) = (n, n)だけ1回しか登場しないので,後でそれを足して2で割る.
nが素因数pをk個含んでいるとしたら,pとqの少なくてもどちらかはpをk個含んでいる.
それぞれの素因数pについて,
 pだけk個含んでいる,qがk個含んでいる(pもk個含んでいるかも)
で最大2^15通り場合分けする.
場合分けすれば,それぞれpとqの取りうる値の数とか取りうる値の和など簡単に求めれるのでそれをかけたり足したりしていけば良い.
メモできる部分はメモしてO(2^15)にしないとTLEになりがち.O(2^15 * 15),O(2^15 * 50)などは厳しい.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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