P17685 [IO 2025 #2] 连续取模
题目描述
给定一个排列 $p_1,p_2,\ldots,p_n$,即从 $1$ 到 $n$ 的每个整数都在数组中恰好出现一次。
你可以进行如下操作:选择下标 $1\le i\le n-1$,将 $p_i$ 替换为 $p_i\bmod p_{i+1}$。由于不能除以 $0$,操作时必须满足 $p_{i+1}\ne0$。这里 $\bmod$ 表示取余运算,在大多数编程语言中用 `%` 表示。
请找出任意一个合法的操作序列,操作次数不超过 $n$,使操作完成后的数组中**至少有一个元素等于 $0$**;或者报告不存在这样的操作序列。注意,**不需要最小化操作次数**。
输入格式
第一行包含整数 $t$,表示测试用例数,满足 $1\le t\le10^4$。
每个测试用例的第一行包含整数 $n$,表示数组长度,满足 $2\le n\le2\cdot10^5$。
第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$,满足 $1\le p_i\le n$。保证从 $1$ 到 $n$ 的每个整数都恰好出现一次。
保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。
输出格式
对每个测试用例,如果不存在符合要求的操作序列,输出 $-1$。
否则,第一行输出操作次数 $k$,满足 $1\le k\le n$;接下来 $k$ 行各输出一个整数 $i$,满足 $1\le i\le n-1$,按执行顺序给出每次操作的下标。任何一次操作若遇到 $p_{i+1}=0$,输出都会被判为错误。所有操作完成后,数组中必须至少有一个元素等于 $0$。
不需要最小化操作次数。如果有多种答案,可以输出任意一种。