← 返回题目列表

AtCoder · agc015_f

F. 古希腊人肯努斯

中文机器翻译题面 查看原题

分数: 1700 点

问题陈述

Kenus,组织者 国际欧几里得奥林匹克正在寻找一对两个整数,需要许多步骤才能使用欧几里德算法找到其最大公约数。

你被给予 Q 查询。的 i-第一个查询表示为一对两个整数 X_i 和 Y_i,并询问您以下问题:在所有两个整数对中 (x,y) 这样 1 ≤ x ≤ X_i 和 1 ≤ y ≤ Y_i,找到最大值 欧几里得步数 (定义如下),以及有多少对具有最大步数,模数 10^9+7.

处理所有查询。这里,一对两个非负整数的欧几里得步数 (a,b) 定义如下:

  • (a,b) 和 (b,a) 具有相同的欧几里得步数。
  • (0,a) 的欧几里得步数为 0.
  • If a > 0 和 a ≤ b,让 p 和 q 是一对唯一的整数,使得 b=pa+q 和 0 ≤ q < a。那么,欧几里得步数为 (a,b) 是欧几里德步数 (q,a) 加上 1.

约束

  • 1 ≤ Q ≤ 3 × 10^5
  • 1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)

输入

输入由标准输入按以下格式给出:

Q
X_1 Y_1
:
X_Q Y_Q

输出

对于每个查询,打印最大欧几里德步数,以及具有最大步数的对的数量,模 10^9+7,中间有一个空格。


样本输入 1

3
4 4
6 10
12 11

示例输出 1

2 4
4 1
4 7

在第一个查询中, (2,3), (3,2), (3,4) 和 (4,3) 的欧几里得步数为 2。没有任何对的步数超过 2.

在第二个查询中, (5,8) 的欧几里得步数为 4.

在第三个查询中, (5,8), (8,5), (7,11), (8,11), (11,7), (11,8), (12,7) 的欧几里得步数为 4.


示例输入 2

10
1 1
2 2
5 1000000000000000000
7 3
1 334334334334334334
23847657 23458792534
111111111 111111111
7 7
4 19
9 10

示例输出 2

1 1
1 4
4 600000013
3 1
1 993994017
35 37447
38 2
3 6
3 9
4 2