题目类型

本题为交互题 / 提交函数题。

拉多和埃米尔在玩一个游戏。拉多先想好一个整数 $X$，满足 $0 \le X < \text{MAX\_X}$；随后埃米尔需要不断提问来猜出这个数。

埃米尔每次可以提出如下形式的问题：

$X + A$ 与 $B$ 的最大公约数是多少？

其中参数必须满足：

• $0 \le A < 2 \times \text{MAX\_X}$
• $1 \le B < 2 \times \text{MAX\_X}$

也就是说，交互库会返回：

埃米尔希望用尽可能小的平均询问次数猜出 $X$。已知拉多选取 $X$ 的方式是完全均匀随机的，也就是说区间 $[0, \text{MAX\_X})$ 中每个整数被选中的概率都相同。

请你帮助埃米尔，编写程序 gcd.cpp 来完成这项任务。你的程序会与评测器程序一起编译，评测器扮演拉多。

实现细节

你需要实现如下函数：

ull play(ull MAX_X);

该函数会被调用很多次（并且每次的 MAX_X 都相同）。你的函数需要返回当前这次游戏中拉多所选的整数 $X$。

为此，你可以多次调用评测器提供的函数：

ull query(ull a, ull b);

该函数会返回：

你的程序：

• 不应包含 main 函数；
• 不应从标准输入读入数据；
• 不应向标准输出打印任何内容；
• 必须包含头文件：

#include "gcd.h"

其中 ull 被定义为 unsigned long long。

在满足以上要求的前提下，你可以自由定义辅助函数、变量、常量等内容。

约束

评分方式

每个测试点单独评分。要在某个测试点上获得分数，你的程序必须：

• 在该测试点的所有 play 调用中都正确猜出 $X$；
• 向 query 传入的参数始终合法。

函数 play 会被调用 $4 \times 10^4$ 次。

设你的程序在某测试点上的平均 query 调用次数为 $Q$，该测试点给定常数 $T_1,T_2$。则你在这个测试点上获得的分数比例为：

• 当 $Q < T_2$ 时：

• 当 $Q \ge T_2$ 时：

测试点

本地测试

官方提供了文件 gcd.h 与 Lgrader.cpp，你可以将它们与你的程序一起编译进行本地测试。

运行程序后，需要输入 MAX_X。随后你的解法会被执行，程序将输出：

• 平均询问次数；或
• 错误信息（若出现错误）。

正式评测所使用的 grader 的行为与提供的本地 grader 一致。

示例交互