A2273. 物品调度
编程题
提高+/省选-
知识点
题目描述
现在找工作不容易，Lostmonkey 费了好大劲才得到 fsk 公司基层流水线操作员的职位。流水线上有 $n$ 个位置，从 $0$ 到 $n - 1$ 依次编号，一开始 $0$ 号位置是空的，其它的位置 $i$ 上有编号为 $i$ 的盒子。Lostmonkey 要按照以下规则重新排列这些盒子。
规则由五个数描述，$q, p, m, d, s$，$s$ 表示空位的最终位置。
首先生成一个序列 $c$，$c_0=0$，$c_{i+1}=(c_i\times q+p)\bmod m$。
接下来从第一个盒子开始依次生成每个盒子的最终位置 $pos_i$，$pos_i=(c_i+d\times x_i+y_i)\bmod n$，$x_i,y_i$ 是为了让第 $i$ 个盒子不与之前的盒子位置相同的由你设定的非负整数，且 $pos_i$ 还不能为 $s$。
如果有多个序列 $x,y$ 满足要求，你需要选择 $y$ 的字典序最小的，当 $y$ 相同时选择 $x$ 字典序最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。
问把所有的盒子移动到最终位置所需的最少步数。
规则由五个数描述，$q, p, m, d, s$，$s$ 表示空位的最终位置。
首先生成一个序列 $c$，$c_0=0$，$c_{i+1}=(c_i\times q+p)\bmod m$。
接下来从第一个盒子开始依次生成每个盒子的最终位置 $pos_i$，$pos_i=(c_i+d\times x_i+y_i)\bmod n$，$x_i,y_i$ 是为了让第 $i$ 个盒子不与之前的盒子位置相同的由你设定的非负整数，且 $pos_i$ 还不能为 $s$。
如果有多个序列 $x,y$ 满足要求，你需要选择 $y$ 的字典序最小的，当 $y$ 相同时选择 $x$ 字典序最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。
问把所有的盒子移动到最终位置所需的最少步数。
输入格式
第一行包含一个整数 $t$，表示数据组数。
接下来 $t$ 行，每行六个数，$n, s, q, p, m, d$ 意义如上所述。
接下来 $t$ 行，每行六个数，$n, s, q, p, m, d$ 意义如上所述。
输出格式
对于每组数据输出一个数占一行，表示最少移动步数。
输入输出样例
输入 #1
1 8 3 5 2 7 4
输出 #1
6
说明/提示
**【样例解释】**
第 $1$ 个到第 $7$ 个盒子的最终位置依次是：$[2, 5, 6, 4, 1, 0, 7]$。
**【数据范围】**
对于 $30 \%$ 的数据，$n \le 100$，
对于 $100 \%$ 的数据，$1 \le t \le 20$，$1 \le n \le 100000$，$0 \le s < n$。
其余所有数字均为不超过 $100000$ 的正整数。
**【提示】**
计算过程可能超过整型范围。
第 $1$ 个到第 $7$ 个盒子的最终位置依次是：$[2, 5, 6, 4, 1, 0, 7]$。
**【数据范围】**
对于 $30 \%$ 的数据，$n \le 100$，
对于 $100 \%$ 的数据，$1 \le t \le 20$，$1 \le n \le 100000$，$0 \le s < n$。
其余所有数字均为不超过 $100000$ 的正整数。
**【提示】**
计算过程可能超过整型范围。