AtCoder Regular Contest 051 B : 互除法

arc051.contest.atcoder.jp

当初の方針

ええ・・・分からない・・・。

aをでかい数で固定してあげたら、
bを見るだけでいいのでは?

Submission #951511 - AtCoder Regular Contest 051 | AtCoder

→ K=30ぐらいまでが限界

無理です。

解法を見て

フィボナッチ数列~?! なんでじゃ~~~

やってみると確かにそうなる。なぜか。

落ち着いて式を整理してみる。


\begin{eqnarray}
gcd(F_{k+1}, F_k) &=& gcd(F_k, F_{k+1} \% F_{k} ) \\
&=& gcd(F_k, ( F_k + F_{k-1} ) \% F_{k} ) \\
&=& gcd(F_k, F_{k-1} \% F_{k} ) \\
&=& gcd(F_k, F_{k-1} ) \\
\end{eqnarray}

おお、すごい。

頭がいいなあ・・・。

Submission #951539 - AtCoder Regular Contest 051 | AtCoder

解説は少し違っていて、gcd(2, 1)が最後の呼び出しになるので、
F_{42} = 267914296 まで計算する必要がある。
たぶん、何かのミス。