AT_agc015_f.[AGC015F] Kenus the Ancient Greek

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

国际欧几里得辗转相除法奥林匹克的主办者けぬす君为了让奥林匹克更加有趣，正在寻找一对使欧几里得辗转相除法迭代次数尽可能大的整数对。

现有 $Q$ 个查询。第 $i$ 个查询由两个整数 $X_i, Y_i$ 给出，询问满足 $1 \leq x \leq X_i$ ， $1 \leq y \leq Y_i$ 的所有 $(x, y)$ 的欧几里得辗转相除法迭代次数的最大值，以及能达到该最大迭代次数的整数对的个数，答案对 $10^9+7$ 取模。

请回答所有查询。欧几里得辗转相除法的迭代次数定义如下，对于任意非负整数 $a,b$ ：

$(a, b)$ 和 $(b, a)$ 的迭代次数相同。
$(0, a)$ 的迭代次数为 $0$ 。
若 $a>0$ 且 $a \leq b$ ，且能表示 $b = pa+q$ （ $0 \leq q < a$ 的整数 $p, q$ ），则 $(a, b)$ 的迭代次数为 $(q, a)$ 的迭代次数加 $1$ 。

输入格式

输入由以下形式组成，从标准输入读入：

$Q$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_Q\ Y_Q$

输出格式

对于每个查询，输出一行，用空格隔开两个整数，分别表示欧几里得辗转相除法的最大迭代次数，以及能达到该最大迭代次数的整数对的个数，对 $10^9+7$ 取模。

输入输出样例

输入#1
```
3
4 4
6 10
12 11
```
输出#1
```
2 4
4 1
4 7
```

输入#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

说明/提示

数据范围

$1 \leq Q \leq 3 \times 10^5$
$1 \leq X_i, Y_i \leq 10^{18} \quad (1 \leq i \leq Q)$

样例解释 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$ 。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页