Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12429 - Finding Magic Triplets (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12429

問題概要

正整数N, K (それぞれ10^5以下) が与えられるので,以下の条件を満たす3つ組(a, b, c)の数を求める問題.
 (a + b^2) mod K = c^3 mod K, 1 ≤ a ≤ b ≤ c ≤ N

解法

bを固定して考える.
aは線形なので,c^3 mod Kがある範囲にあるcの数を高速に計算できれば良く,Fenwick treeを使う.
bを1ずつ変えていった時,cの取りうる値は1個減るか増えるかなので,Fenwick treeの修正もすぐ可能.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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