问题 6160 --NOI2010湖北省选 一试 第3题 物品调度

6160: NOI2010湖北省选 一试 第3题 物品调度

时间限制: 1 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

题目描述

Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置,从0到n-1依次编号,一开始的初始状态为:0号位置为空位,对0<i<n,i号位置上有编号为i的盒子。Lostmonkey要按以下规则重新排列这些盒子。 重新排列的规则由5个数q,p,m,d,s来描述,其中s表示要求s号位置最终为空位。为了确定所有盒子的最终位置,首先生成一个序列c,c0=0,ci+1=(ci*q+p) mod m。然后从编号为1的盒子开始按编号从小到大的顺序依次生成每个盒子的最终位置直到给编号为n-1的盒子生成最终位置。假设编号为i的盒子最终被放到posi号位置,那么posi=(ci+d*xi+yi) mod n,其中xi和yi是为确保编号为i的盒子不与编号小于i的盒子放到相同位置而由你设定的非负整数,且posi不能为s。若有多个xi和yi满足要求,你必须选择最小的yi,在yi相同时必须选择最小的xi。 这样,根据以上规则你可以确定所有盒子的最终位置,也就是终止状态。 假设通过一次移动你可以把某个盒子移到空位上,移动后被移盒子原来所在位置变成空位。 请问最少需要多少次移动才能把所有盒子从初始状态转换成终止状态?

输入

第一行是一个整数t,表示数据组数(每组数据描述一个要重新排列的问题)。接下来从输入文件第二行开始有t组数据,每组数据只有一行,是用空格隔开的六个整数n,s,q,p,m,d,其含义如上所述。输入的数据保证30%的数据满足n≤100。100%的数据满足t≤20,n≤100000,s<n。其余的所有数字均为不超过100000的正整数。

输出

包含t行,第i行输出对输入中给出的第i个重新排列问题把所有盒子从初始状态转换成终止状态需要的最少移动次数。


样例解释:在终止状态,编号为1的盒子到编号为7的盒子依次被放到2,5,6,4,1,0,7号位置。计算过程中表示式的值可能超过整型范围。

样例输入

1
8 3 5 2 7 4

样例输出

6

提示

来源

[提交][状态]