AGC015-F(Kenus the Ancient Greek) 解説

初めて解説記事を書くので至らぬ点もあると思いますが、よろしくお願いします。

では、行きましょう。

問題概要

$Q$ 個のクエリで整数 $X,Y$ が与えられる。 $X$ 以下の $A,Y$ 以下の $B$ からなるペア $(A,B)$ のうち、ユークリッドの互除法の反復回数が最多となるものを求め、またその回数となるようなペアの数を出力せよ。

ステップ1 反復回数の最大値

まず、 $X_i$ と $Y_i$ を逆にしても結果は変わらないので、以降は $X_i \leq Y_i$ となるように $swap$ されているとします。

反復回数が $N$ 回となるようなペアを列挙して(ただし、ペアの $1$ つめの要素が $2$ つめの要素より小さいとします) $sort$ した時に一番先頭に来るペアが、反復回数が $N$ 回となるペアの中で $1$ つめの要素が最小( $sort$ した時点でこれは満たされる)かつ $2$ つめの要素が最小だとします。

この時、反復回数が $N$ 回となるようなペアの中で一番小さいペアを $(a,b)$ とすると、反復回数が $N+1$ 回となるようなペアの中で一番小さいペアは $(b,a+b)$ です。

このような性質があれば反復回数の最大値を求められるのが楽そうです。

ではこの性質が満たされる $N$ はあるのでしょうか。実は最小で $N=2$ のときが満たし、これより $N\geq2$ のときこの性質が満たされることが分かります。

反復回数が $2$ 回となるようなペアの中で一番小さいペアは $(2,3)$ です。(ペアの小さい方の数字が $0$ なら反復回数は $0$ で、 $1$ なら $1$ になるためです。出力例 $1$ の説明からでもこの事実は導けると思います。)

よって、反復回数が $3$ 回のペアのうち最小のものは $(3,5)$ 、 $4$ 回のペアのうち最小のものは $(5,8)$ ...とフィボナッチ数列的に求められます。後は各クエリごとに反復回数が $n$ 回のペアを作れるか調べればよいです。(二分探索でもよいですが、フィボナッチ数列の第 $100$ 項は $10^{18}$ を軽く超えるので全探索でも十分間に合います)

また、反復回数の最大値が $1$ となるようなクエリの判定は $X_i$ が $2$ 未満または $Y_i$ が $3$ 未満のどちらかが満たしているかをチェックすればよいです。

ステップ2 反復回数の最大値をとるペアの数

反復回数の最大値を $Z$ とします。

まず $Z=1$ の時、0が含まれていなければ必ず反復回数は $1$ になるので、答えは $X_iY_i$ です。

以降は $Z\geq2$ の場合を考えます。

反復回数が $T$ 回となるようなペアをあらかじめ全て列挙して、それを作ることができるかを判定すればよいですが、 $(2,3),(2,5),(2,7)$ ...の反復回数は全て $2$ 回であり、これは難しいです。しかし、 $(2,3+2t)$ は全て反復回数が $2$ 回であることを利用すると、 $3+2t \leq Y_i$ を満たす $t$ の最大値を求め、これをペアの数に足し合わせばよいです。

これを利用すると、反復回数が $T$ 回となるようなペアを全て列挙するときに、そのペアを $(a,b)$ としたときに、 $b \leq 2a$ が満たされるもののみ(かつ、反復回数が $T+1$ 回で最小のペアより小さいもの)を列挙すればよいです。さて、そのようなペアはいくつあるでしょうか。

実はこれは $T$ 個です。

まず、 $T=2$ の場合、条件を満たすペアは $(2,3),(3,4)$ の $2(=T)$ 個です。

$T=3$ の場合、 $1$ 回反復させると左に述べたようなペアになるようなペアは $2$ 個あります。そして、 $(a,b)$ に対して $(b,2b-a)$ も満たすことが分かります。この場合は $(3,5)$ に対して $(5,7)$ のみが満たされます。このような操作を $Remake$ とします。この時、 $Remake$ ができる回数は反復回数が $T$ 回のなかで最小のものは $1$ 回、それ以外のペアは $0$ 回と分かります。( $T$ が小さい範囲で実験すれば導くことができます。)よって、 $3$ 個です。以降も同様に示せます。

よって、反復回数が $T+1$ 回となるペアを列挙するとき、反復回数が $T$ 回となるようなペアを $(a,b)$ としたとき、 $T+1$ 回となるペアの候補に $(b,a+b)$ を追加します。そして、それらの中で最小のものを選び、 $(a,b)$ としたとき、 $(b,2b-a)$ を追加すればよいです。

この後は、列挙した反復回数が $Z$ 回となるペアに対して、それが作れるか(作れるとき何通り作れるか)を判定すればよいです。この時、 $X_i$ と $Y_i$ を $swap$ しても作れる場合があるので注意してください。

計算量は時間制限が $5$ 秒のこともあり、前準備も各クエリの処理も十分間に合う速度で行えます。