No.195

$F_{1,1}(n) = F_n$ (通常のフィボナッチ数) とすると, $F_{40} \gt 10^9$ となるので, $i, j, k \leq 39$ である.

また, $F_{A, B}(n)$ を初項から順に計算すると,

$$F_{A,B}(n) = AF_{n-2} + BF_{n-1} \ (n \geq 3)$$

となる.

$X = Y = Z$ の場合:

$X = 1$ であれば, $A = B = 1$ が最小である.

$X \geq 2$ であれば, $i = 3, A = 1, B = X - 1$ とすれば $A$ を $1$ にできるので, $i \geq 4$ のときにそれより小さな $B$ が求められるか調べればいい.

$X, Y, Z$ のうち 2 つが同じ場合:

$X \neq Y$ とする.

$i, j$ を決めれば連立1次方程式を立てることができるので, $A, B$ が求められる. $i, j$ を動かしてすべての $A, B$ の組み合わせを求め, その中から題意を満たすものを選べばいい.

$X, Y, Z$ がすべて異なる場合:

$i, j$ を動かして $A, B$ の組み合わせを求めるところまでは同じである. さらにこの場合は $A, B$ を求めた後に, $k$ が存在するかどうかを調べる処理が追加される.