P12417 基础构造练习题 1

2025.5.6：加强操作次数限制，并调整了部分分设计。 2025.5.8：再次加强操作次数限制，并调整了部分分设计。之前的提交记录已经全部重测。

有一列实数，对于**每一次**操作，可以选择两个实数，把它们同时变为两数之积。 例如，给定 $7, 4, 5$，对 $7$ 和 $5$ 进行一次操作，原数列变为 $35, 4, 35$。 给定数列的长度 $n$，你的目标是找到一种操作方案，使得对于任意长度为 $n$ 的实数列，按照该操作方式操作之后，数列的每一项数值都相同。

**本题有多组测试数据。** 第一行输入数据组数 $T$。 对于每组数据有一行，包含一个正整数 $n$，表示数列长度。

对于每组数据，先输出一个整数表示能否找到。若能输出 $1$，否则输出 $0$。 若能找到，还需要输出一行 $m$ 表示操作次数（你需要保证 $0 \leq m \leq 5 \times 10^5$），接下来 $m$ 行，每行包含两个整数，表示操作的两项在数列中的编号。

Idea：Milmon，Solution：Milmon & _fewq，Code：Milmon & _fewq，Data：Milmon，Check：Konata28。 对于所有测试数据，保证 $T = 20$，$2 \leq n \leq 2^{10}$。本题共包含 $3$ 个子任务： | 子任务编号 | 分值 | 测试点数目 | | :-: | :-: | :-: | | $1$ | $10$ | $1$ | | $2$ | $30$ | $1$ | | $3$ | $60$ | $3$ | 对于子任务 1，选手只需要正确回答是否存在操作方案即可获得满分。 对于子任务 2，对于每组测试数据分别计分：对于一组测试数据，只要选手正确回答是否存在操作方案，并且给出的操作方案均合法，就可以得到该测试点 $5 \%$ 的分数。选手在该测试点得到的分数等于每组测试数据得分的总和。 对于子任务 3： - 若存在一组测试数据，选手没有正确回答是否存在操作方案，或者给出的操作方案不合法，那么选手在该测试点不得分； - 否则，若对于所有存在操作方案的测试数据，选手都给出了操作次数不超过 $2n - 1$ 的方案，那么选手在该测试点得到全部分数； - 否则，设所有存在操作方案的测试数据中选手给出的最大操作次数为 $s$，定义函数： $$ f(x) = \frac{2 \times 10^7}{(x + 4\,000)^{0.7}} $$ 则选手在该测试点的得分为： $$ \frac{f(s) - f(500\,000)}{f(2\,047) - f(500\,000)} \times 55 $$ 下表为在一些特殊的 $s$ 中选手在该测试点得到的分数： | $s =$ | 选手得分 | | :-: | :-: | | $500\,000$ | $0$ | | $400\,000$ | $0.436$ | | $300\,000$ | $1.106$ | | $200\,000$ | $2.302$ | | $100\,000$ | $5.258$ | | $50\,000$ | $9.836$ | | $10\,000$ | $29.402$ | | $5\,000$ | $41.003$ | | $3\,000$ | $49.391$ | | $2\,047$ | $55$ | 提示：若能够完成正确性判断，但是无法完成构造的，也需要按照输出格式输出，例如你可以输出一个 $m = 0$ 的构造。类似地，输出时请判定 $0 \leq m \leq 5 \times 10^5$ 是否成立，若评分时存在一组数据的 $m > 5 \times 10^5$，则你无法得到任何分数。