よって背理法より、隣り合うフィボナッチ数は互いに素となります。Fib(x-1)Fib(y)という性質が成り立ちます。数学的帰納法を使うと証明できるそうですが、ここでは簡単に上の定理が正しいことを説明します。Fib(x)は階段を1段ずつ、または1段飛ばしで登っていき、x段目に辿り着いたときの上り方のパターン数と考えることができます。Fib(x+y)はx+y段目まで登るとき(最下段からx+y-1段登ったとき)のパターン数です。y-1段登るパターン数)ということで、まさにこれが加法定理と同じです。Fib((x,y))さて、いよいよ目的の定理を考えます。Fib(x)とFib(x+y)の最大公約数を考えてみます。1より)はい、来ました。x+y))となります。よって、目的の定理が成り立ちます。1000000007で答えよ。[a]はaの整数部を表す。方針こういう数論系の問題は好きです。Editorialのように式変形していくと、メルセンヌ素数と関連する値になることがわかります。1が素数となるためには、pは素数でなくてはいけません。1で10は素数ではないため、1023は素数ではありません。いや、、こんなことしなくても、1023は3で割れることが一目瞭然なので、素数じゃないのは明らかか。蛇がN*Mサイズのブロックを動き回る。りんごに辿り着くまでに蛇が移動しなければならない最小移動数を求めよ。方針(蛇の頭の座標、蛇の体部の相対座標)を状態数にしてBFSする。この「相対座標を状態数にとる」という発想はおもしろいと思いました。各部位について、相対座標は2bitで表現します。蛇の体部は最大で8つの部位から成り立っているので、全体として2^16あれば頭以外の部分の位置を表現できます。Chromeに「JSONView」を入れました。これで、ブラウザから綺麗にインデントされたJSONを見ることができます。日本語もエスケープされていない状態で表示されます。CHROME」を押すだけです。https://chrome.google.com/webstore/detail/chklaanhfefbnpoihckbnefhakgolnmc便利すぎる。早く入れておけばよかった。開発環境2012年9月9日日曜日gitチートシート自分用メモ。最新のコミットcheckouthoge.txtをindexの状態に戻す。hoge.txtカレントディレクトリ配下をindexの状態に戻す。.hoge.txtをHEADの状態に戻す。hoge.txtcommit直前のコミットを修正する。--amendconfigデフォルトのエディタを変更する。emacsdiff空白文字の変量を無視して差分を取る。treeとindexの差分をとる。treeとHEADの差分を取る。treeと1つ前のコミットの差分を取る。HEAD^indexとHEADの差分を取る。--cached色を付けてdiffを見やすくする。--colorファイルの内容は表示せず、ファイル名のみ表示する。--name-onlyreset直前のコミットを取り消す。HEAD^直前のコミットを取り消す。2)結果ひさびさにプロコンに参加した。Emacs)でうまく書けるか不安だったが思ったより鬼は黒くなかった。3/5AC、160位/1925人だった。Errorで死んでいた。それがなかったら20位くらいだった。)問題D、Eがおもしろかった。