题目描述

题目译自 PA 2024 Runda 5 Dzielniki

我们从区间 $[1,n]$ 中选取了一个整数 $x$，你的任务是猜这些数。你不必盲目地猜，可以问一些问题。每个问题你可以询问区间 $[0,c]$ 中的某个整数 $y$，我们会告诉你 $x+y$ 的因子个数。

为了让题目稍微困难一些，你需要在一次运行中解决 $t$ 个用例。询问总数被限制在 $q$ 次。

使用交互库交互

请注意：由于 LibreOJ 的实现与 PA 中所用 OJ 不同，因此这部分交互方式与原题有一些区别。

在程序的开头你应该使用 #include "dzilib.h" 引入交互库。

你需要实现如下函数来完成本题。

• void Solve()：程序只会调用此函数一次，在这个函数中，你需要实现猜测 $t$ 个用例的所有程序逻辑。

你可以调用如下函数。

• int GetT()：返回 $t$ 的值。
• long long GetN()：返回 $n$ 的值。
• int GetQ()：返回 $q$ 的值。
• long long GetC()：返回 $c$ 的值。
• int Ask(long long y)：返回要猜的数 $x$ 与 $y$ 的和的因子个数。你需要保证 $0\le y\le c$。
• void Answer(long long x)：做出一次回答。此函数无返回值。

如果你调用 Ask() 函数的总次数超过 $q$，则你的程序会被判为 Wrong Answer。如果存在一次调用 Answer() 函数，你猜测的数与答案不同，你的程序也会被判为 Wrong Answer。

使用 I/O 交互

与 PA 题目不同的是，在 LibreOJ 上，你可以使用标准输入输出与交互库交互。

首先你需要从标准输入中读取四个整数 $t,n,q,c$，意义如题目描述。

接下来开始交互过程。

• 如果想要做出一次询问，则按 ? y 的格式向标准输出写入一行，其中 $y$ 代表你的查询。接着你需要从标准输入中读取一个整数，表示交互库做出的回答。
• 如果想要做出一次回答，则按 ! x 的格式向标准输出写入一行，其中 $x$ 代表你的回答。接着你需要从标准输入中读取一个整数，如果这个整数为 $0$，则表示你的回答错误，你需要立刻停止你的程序，否则这个整数将为 $1$，请忽略这个整数，继续下一组数据的交互。
• 当所有 $t$ 组数据交互结束时，你需要立刻停止你的程序。

交互库

所有测试点中的 $x$ 和它们的顺序都是预先确定好的。这意味着交互库行为不会根据你的程序行为而进行调整。

样例交互

样例中，有 $t=2,n=10^6,q=10^4,c=10^{15}$，要猜的数分别为 $1000$ 和 $1$。一组样例交互过程如下表：

交互过程中提出了 $2$ 次询问，未超出 $10\, 000$ 次询问的限制。请记住，一组数据中所有测试点的总查询次数才是最重要的。

数据范围与提示

详细子任务限制如下表所示。在一个子任务中，$t,n,q,c$ 的值都相同。

样例不属于任何子任务，可以在样例错误的情况下得分。