Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12401 - Metal Powers (この記事を編集する[管理者用])

Source

7th Contest of Newbies (2011-12-31)
UVa 12401

問題概要

a = (1+sqrt(5))/2, b = (2+sqrt(8))/2, c = (3+sqrt(13))/2 とする.
a^n, b^n, c^n を最も近い整数に丸めたものを答える問題.nは10^8以下.
ただし,答えが10桁以上になるなら,最初の3桁と最後の3桁と桁数を求める.
問題文に書かれているヒントは,a^n + (1-a)^nは任意のnについて整数になる.
a^n, b^n, c^nはそれぞれ,nが大きくなると,整数に近づく,など.

解法

b^n + (2-b)^n,c^n + (3-c)^nも常に整数で,
例えば,b^n = x + y sqrt(8)と書くと,(2-b)^n = x - y sqrt(8)となるので,
nが大きいときは,b^nに最も近い整数は2xになる.
nが小さい時は,doubleで計算して,そのまま出力する.
桁数と上3桁を求めるのは,doubleで対数を計算すればなんとかなる.
下3桁は,上の事実から,x, yに対する漸化式を立てて行列べき乗に落として,mod 1000で計算する.
ただし,行列の各要素は,半整数 (1/2の倍数) になるが,その行列をいくつ掛けても半整数でかけるという性質がある.
ので,行列を2倍しておいて,掛け算するたびに,1/2倍しておくなどして,うまく計算する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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