Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12341 - Next to Never (この記事を編集する[管理者用])

Source

ACM ICPC Regional Warmup 2011 (2011-10-29)
UVa 12341

問題概要

初項がa,公比がp/qの等比数列の無限級数が収束してN以下になるような,(p,q)の組の数を考える.
pは0以上M以下,qは1以上M以下でなくてはいけない.
a, N, Mが与えられた時,条件を満たす(p,q)の組の数と,更に,条件を満たす(p,q)が互いに素なものの数を求める問題.
aは1以上5以下,Nは1000以上10000以下,Mは20000以上100000以下で,テストケースの数は550以下.

解法

条件を満たさないものの方が圧倒的に少ないので,それをカウントすることにする.
クエリをa/Nの値でソートしておくと,条件を満たさないものは徐々に増えていくようにでき,条件を新しく満たさなくなったものをカウントしていった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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