分数: 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