AT_agc015_f [AGC015F] Kenus the Ancient Greek

[problemUrl]: https://atcoder.jp/contests/agc015/tasks/agc015_f 国際ユークリッドの互除法オリンピックの主催者であるけぬすくんは、 オリンピックをより面白くするため、$ 2 $ 数のペアに対してユークリッドの互除法を走らせたとき、反復回数ができるだけ大きくなるようなペアを探しています。 $ Q $ 個のクエリが与えられます。$ i $ 個目のクエリは、$ 2 $ つの整数 $ X_i,Y_i $ で表され、 $ 1\ ≦\ x\ ≦\ X_i,\ 1\ ≦\ y\ ≦\ Y_i $ なるような $ (x,y) $ のペアの中での、ユークリッドの互除法の反復回数の最大値と、その最大値をとるペアの個数を $ 10^9+7 $ で割ったあまりを求めるクエリです。 全てのクエリに答えてください。ただし、ユークリッドの互除法の反復回数とは、任意の非負整数 $ a,b $ に対し、 - $ (a,b) $ と $ (b,a) $ の反復回数は等しい - $ (0,a) $ の反復回数は $ 0 $ - $ a\ >\ 0 $ かつ $ a\ ≦\ b $ なら、整数 $ p,q $ $ (0\ ≦\ q\ を用いて\ b $ を $ b=pa+q $ と一意的に表したとき、$ (q,a) $ の反復回数に $ 1 $ を加えた値が $ (a,b) $ の反復回数となる を満たすように定義されます。

N/A

N/A

### 制約 - $ 1\ ≦\ Q\ ≦\ 3\ ×\ 10^5 $ - $ 1\ ≦\ X_i,Y_i\ ≦\ 10^{18}(1\ ≦\ i\ ≦\ Q) $ ### Sample Explanation 1 $ 1 $ つ目のクエリでは、$ (2,3),(3,2),(3,4),(4,3) $ のユークリッドの互除法の反復回数が $ 2 $ 回です。$ 3 $ 回以上反復が必要な組はありません。 $ 2 $ つ目のクエリでは、$ (5,8) $ のユークリッドの互除法の反復回数が $ 4 $ 回です。 $ 3 $ つ目のクエリでは、$ (5,8),(8,5),(7,11),(8,11),(11,7),(11,8),(12,7) $ のユークリッドの互除法の反復回数が $ 4 $ 回です。