题目类型说明

这是一道提交函数题 / 库调用题。你需要实现指定函数，不需要编写 main 函数，也不能从标准输入读取或向标准输出写入。

你需要实现：

std::vector<int> guessPermutation(int n);

评测程序会提供：

long long lcm(int i, int j);

---

题目描述

Marti 拥有一个随机生成的排列 p，它由数字 1,2,3,\dots,n 组成。Radko 想知道这个排列，但 Marti 不愿意直接告诉他，只会回答下面这一种问题：

p_i 和 p_j 的最小公倍数是多少？

不幸的是，Radko 太忙了，于是把这件事外包给了你。

你的程序会在每个测试上被调用 n_tests 次。你的最终成绩将依据：在这一批排列中，你为找出某个排列所使用的最大提问次数来计算。

请特别注意时间限制。

---

实现细节

你需要实现函数：

std::vector<int> guessPermutation(int n);

该函数会在每个测试上被调用 n_tests 次，参数为排列长度 n。函数应返回一个长度为 n 的数组，表示当前需要恢复的排列。

评测程序提供函数：

long long lcm(int i, int j);

你可以调用该函数任意多次。参数 i 和 j 为两个不同的下标，且满足 1 <= i, j <= n。函数返回 p_i 与 p_j 的最小公倍数。

该函数的时间复杂度为：

$$O(\log^2 n).$$

你的程序必须：

• 实现函数 guessPermutation；
• 不能包含 main 函数；
• 不能从标准输入读取，也不能向标准输出写入；
• 必须包含头文件：

#include "lcm.h"

除此之外，你可以自由定义辅助函数、变量、常量等。

---

限制说明

• 每个排列都是随机生成的。

---

子任务与评分

你在某个子任务上获得的分数比例，取决于你在该子任务上单个测试中使用的最大询问次数 $q_{\text{participant}}$，以及该子任务给定常数 $q_{\text{author}}$。

若

$$q_{\text{participant}} \le q_{\text{author}},$$

则

$$\text{score} = 1.$$

否则：

$$\text{score} = 1 - \sqrt{1 - \frac{q_{\text{author}} + 1}{q_{\text{participant}} + 1}}.$$

子任务表

子任务	分值	$n$	$q_{\text{author}}$	$n_{\text{tests}}$
1	20	10	13	5 000 000
2		100	106	500 000
3		1 000	1 002	50 000
4		10 000	10 001	5 000
5		100 000	99 999	500

---

本地测试

题目提供文件 Lgrader.cpp，可用于本地测试。使用时，需要在你的代码中加入：

#include "Lgrader.cpp"

本地 grader 的输入格式如下：

• 第一行输入两个整数 n 和 n_tests；
• 接下来有 n_tests 组测试，每组测试输入 n 个整数，表示该组对应的排列。

如果你的程序对所有测试都恢复出了正确排列，那么最后会输出：

• 你在某一组排列上使用的最大询问次数。