Problem2087--停车场

2087: 停车场

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

有一个圆形的停车场,里面有n个停车位。停车位的编号从0至n-1,因为停车场是圆形的,所以第n-1个停车位的下一个停车位就是第0个停车位。

一开始所有停车位都是空的。现在有n台汽车排队进来停车,只有前面进去的车已经停好位置了,那么下一台汽车才能进入停车场。

n台汽车的编号是从0至n-1, 注意:汽车的编号与停车位的编号不是直接对应关系,第i台汽车不一定停在第i个停车位。

确切一点说,第i台汽车最喜欢停在第p[i]个停车位,但是如果在它前面进场的汽车已经把该停车位占据了,

那么第i台汽车就会从第p[i]+1个停车位开始往后搜索,一旦找到一个空的停车位,第i台汽车就停在那个空的停车位。

容易发现,一台汽车在找到合适的停车位之前,可能出现多次“冲突”。

例如第i台汽车最喜欢停在第p[i]个停车位,但是第p[i]个停车位被占了,那么就“冲突”1次,

然后第i台汽车就想停在第p[i]+1个停车位,如果第p[i]+1个停车位也被占了,那么又多了1次“冲突”,......

问当所有的汽车都停车结束以后,停车过程中,总共产生了多少次冲突?





输入格式

输入文件名:park.in

多组测试数据。

第一行,一个整数G,表示有G组测试数据。1<=G<=10。

每组测试数据格式如下:

一行,4个整数:n,A,B,C。1<=n<=250000。0 <= A,B,C < n。

其中A,B,C三个整数的作用是用来产出p[i]的。

P[i] = (A*i*i + B*i + C) % n,  其中 0<=i<n。



输出格式

输出文件名:park.out

共G行,每行一个整数。



输入/输出例子1

输入:

5

47 0 1 0

47 0 0 42

30 1 1 1

250000 2352 32652 199975

250000 0 0 248987



输出:

0

1081

175

93375000

31249875000






Sample Input Copy

5
47 0 1 0
47 0 0 42
30 1 1 1
250000 2352 32652 199975
250000 0 0 248987

Sample Output Copy

0
1081
175
93375000
31249875000

Source/Category