Source: Petrozavodsk Winter 2022, Day 6. ICPC Camp Day 1, PKU Contest, Problem E.

本题是交互题。

本题交互格式，交互要求均有细微差别，但是 std 不依赖这些差别，你可以尝试解决原题：

• 原题额外要求 $1\le x\le 10^{18}$。

题目描述

这是一道交互题，注意本题交互格式与原题不同。

Alice 有一个 $[1,10^{18}]$ 的整数 $y$ ，而 Bob 想要求出这个数，所以 Bob 每次会选一个 $[0,10^{18}]$ 的整数 $x$ 向 Alice 提问。如果 $y>x$ 则 Alice 返回 $2$ ，如果 $y=x$ 则 Alice 返回 $1$ ，如果 $y<x$ 则 Alice 返回 $0$。

然而，Alice 和 Bob 的通信被 Eve 截获了。Eve 写了一个伪随机数生成器：

const long long P=998244353; // 不一定是这个数。
const int n=3; // 也不一定是这个数。
long long seed=233; // 更不一定是这个数。
int gen()
{
    seed=seed*n%P;
    return seed%n;
}

每次 Alice 返回一个数 $a$ 时，Eve 会用这个伪随机数生成器生成一个数 $b$ ，并给 Bob 返回 $a\oplus b$（异或，即 c++ 里的 ^ ）。

你是 Bob ，并且你用一些操作得到了 $\texttt P$ 和 $\texttt n$ ，但是你不知道 $\texttt{seed}$ 。你需要在 100 次询问内得到 $y$。

实现细节

你不需要，也不应该实现 main() 函数，或在任何文件与标准输入/输出流中读入或输出任何信息。

你只需要包含头文件 guess.h，并实现以下函数：

void init(int subtask_id,int T);
long long solve(long long P,int n);

• init 函数会被恰好调用 $1$ 次。
• • 参数 subtask_id 表示当前测试点编号，参数 T 表示当前测试点有几组数据。
• solve 函数会被调用 $T$ 次。
• • 参数 n 和参数 P 即为 Eve 的伪随机生成器的参数。你需要返回 Alice 的数 $y$ 。

你可以调用以下函数：

int query(long long x);

• 参数 x 表示 Bob 向 Alice 提问的数。
• 你需要保证 $0\le x\le 10^{18}$。
• 返回值已经被 Eve 修改过了。

样例交互库

在下发文件中，你可以找到样例交互库 grader.cpp ，你可以通过交互库的实现来帮助你理解并实现这道题目。需要注意的是，在进行最终测试时，交互库的实现与样例交互库有所不同，因此你不应当依赖此交互库的实现。

样例交互库将通过以下格式在标准输入中读入数据：

• 第一行，两个正整数 $\texttt{subtask\_id}$ 和 $\texttt T$。
• 接下来 $T$ 行，每行四个整数 $\texttt P,\texttt n,\texttt{seed},y$ ，表示一组测试。

交互过程中，如果出现任何错误，交互库会直接输出错误信息并退出。否则，交互库会在最后输出询问次数的最大值。

你可以在终端使用以下命令来编译你的程序：

g++ grader.cpp guess.cpp -o guess.exe -O2

在最终评测时，对于任何合法的（使用不超过 $Q_\text{max}$ 次询问操作）交互过程，保证交互库使用的时间不超过 $0.1$ 秒，使用的内存不超过 $2\texttt{MB}$。

样例

以下是一组可能的对样例交互库的输入。

0 1
998244353 3 332748118 3

交互库调用	选手程序调用	返回值
init(0,1)
solve(998244353,3)
	query(4)	$1$
	query(2)	$2$
	query(3)	$1$
		$3$

在这次交互过程中，选手程序猜到了 $\texttt{seed}$ ，从而只有第一次的返回值需要异或 $1$。

数据范围与提示

如果你在某个测试点中没有在时间限制与空间限制内返回结果，或发生了运行时错误，或最终返回的答案不正确，则你在该测试点的得分为 $0$。

否则，设 $Q$ 为你在该测试点中调用函数 query 的次数，$S$ 为该测试点的满分，则：

• 若 $Q_\text{max} < Q$，则你的得分为 $0$。
• 若 $Q_\text{min} < Q \leq Q_\text{max}$，则你的得分为 $S \cdot \left( 1 - 0.7 \cdot \dfrac{Q - Q_\text{min}}{Q_\text{max} - Q_\text{min}} \right)$。
• 若 $Q \leq Q_\text{min}$，则你的得分为 $S$。

在一个子任务中，你所得到的分数即为所有测试点分数的最小值。

对于所有数据， $10^3\le P\le 10^{18},3\le n\le 4,0\le \texttt{seed}<P,T\le 100,Q_{\min}=100,Q_\text{max}=200$ ，保证 $P$ 为质数。

子任务	$P\le$	特殊限制	分值
$1$	$10^4$	$T=1$	$20$
$2$	$5\times 10^6$		$15$
$3$	$10^9$	$T\le 10$
$4$	$10^{18}$	$n=3$	$20$
$5$		$n=4$
$6$			$10$