スポンサーサイト

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

April Cook-Off 2012

2012/04/23
April Cook-Off 2012

Tags : プログラミング CodeChef 未解決

問題

問題セットの原文はここを参照。

RESIST. Resistance

問題文中の 2 つめの図のような N 段の電気回路がある。
ここで、右端の端子対は短絡している。
この回路の電気抵抗を有理数で求めよ。ただし、分母、分子をそれぞれ mod M で求めたあと、約分して出力すること。

1 ≦ N ≦ 10^6
2 ≦ M ≦ 2^30

解答

RESIST.
回路の右端から順に抵抗を合成していけば、法則がみえてくる。
N = k のときの ( mod をとる前の ) 答えを q/p とすると、
N = k+1 のときの答えは (p+q)/(2・p+q) となる。
これは、分母、分子それぞれで、Fibonacci 数列を一つおきに見ていることになる。
たとえば、
・ N = 1 のとき q/p = 1/1
・ N = 2 のとき q/p = 2/3
・ N = 3 のとき q/p = 8/5
など。

Fibonacci 数列の隣接する二項は互いに素だから、約分がどうとかいう制約はないものと同じ。
なので、単に N 回ループを回すか、より高速には繰り返し二乗法を使えば答えが計算できる。
http://www.codechef.com/viewsolution/988271
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。