AGC015-F Kenus the Ancient Greek

問題概要

$Q$ 回にわたって整数 $X,Y$ が与えられる。 $0\leq x\leq X,0\leq y\leq Y$ を満たす整数 $x,y$ の組で、Euclid の互除法を走らせた時の反復回数の最大値と、それを導く組の個数を求めよ。

解法

まず、最大値を求めることを考える。回数ごとに組の最小値を貪欲に考えていくと、フィボナッチ数列に帰着され、簡単に回数が求まるところまでは明らかだろう。

フィボナッチ数列は、 $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n(n\in\mathbb{N})$ と定義しよう。

ここで、フィボナッチ数列の性質に注目すると、 $n\geq 3$ では $F_{n+1}\lt 2F_n$ を満たす。これを考えると、ある組を $m(\geq 2)$ 倍したものが可能なら、その次の組も使えて、その組の操作回数が最大だったことに矛盾するため、答えとして求まる組は互いに素である。

次に、このような組の個数を数えることを考える。実は、組としてありうるものは、最大回数を $N$ 回として、 $i,k\in\mathbb{N},i\lt N$ をみたす $i,k$ を用いて $(x,y)=(F_{N+1}+kF_{i+2}F_{N-i-1},F_{N+2}+kF_{i+2}F_{N-i})$ と表せる。

互除法の操作を後ろから考えると、どこかで、 $2$ 以上の整数 $a$ を用いて $G_{n+2}=aG_{n+1}+G_n$ のように漸化式の過程が変化して数列が生成される場合も、操作回数は変わらないことがわかる。このように途中で別の漸化式を用いることを「逸脱」と呼ぼう。

組から数列は一意に定まるので、逸脱も含めて、題意を満たす組を生成する数列の個数を数えればよい。

実は、逸脱は題意を満たす組を導く数列を生成する過程で、 $n\leq N-1$ では高々 $1$ 回しか起こらない。また、そのとき必ず $a=2$ である。これは、先ほど述べたフィボナッチ数列の性質をもとに示せる。これから、組を表す式が導けて、また、この事実から、 $n\leq N-1$ 、つまり $i\leq N-2$ であれば $k=1$ となることもわかる。