Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12355 - Consecutive Sums (この記事を編集する[管理者用])

Source

ACM-ICPC Asia Phuket Regional Semilive (2011-11-06)
UVa 12355

問題概要

p+q個の連続する整数 (後半のq個はすべて正) で,最初のp個の和と,最後のq個の和が等しくなることがある.
q (10^14以下) が与えられるので,考えうるpの値の数は何通りあるかを求める問題.

解法

連続する整数の最初をaとおけば,
 (a + a+p-1) * p / 2 = (a+p + a+p+q-1) * q / 2
となり,これをaについて解けば,詳細は忘れたので適当だけども
 a = (p+q+1)/2 + pq/(p-q)
だったか,そんな感じの形になる.(多分符号とかいろいろ間違えてるのでちゃんと計算してください)
aが整数になり,pがqより大きいものの数を求めれば良い.
 p = q + k
と置くと,pq/(p-q)が整数か半整数でなければいけないので,
 pq / (p-q) = (q + k) q / k = q^2 / k + q
なので,kは2q^2の約数でないといけないことがわかる.
後,kが2の倍数なら (p+q+1)/2 が整数でなく, 2q^2/k が整数であってはいけない.
また,kが2の倍数じゃないなら…,も同様な議論をし,条件をみたすものをカウントすれば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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