问题 1265. -- Random Generator

1265: Random Generator

时间限制: 1 Sec  内存限制: 128 MB
提交: 836  解决: 93
[提交][状态][讨论版]

题目描述

随机数生成器是一种很重要的工具,但是 williamchen 的智力堪忧,只会用一种非常蠢的方式获得随机数。
具体方法是,他会给出正整数A, 正整数B,正整数C, 这三个整数都小于1001,他获取的第一个随机数就是A。
接下来,他将上一次获得的随机数乘以B再加上C, 最后对 1001 取模,得到一个新的随机数。
重复上述的过程,他可以获得任意多的随机数。
数学化地描述则是 a(0) = A, a(k+1) = [a(k) ∗ B + C] mod 1001
现在他想要问你,假如他按照这样的方式生成了 n 个随机数,那么其中第 k大的数是哪个。

输入

包括多组测试数据,第一行给出数据组数T, T <= 5。

接下来每组数据第一行包括三个整数A,B,C,0 <= A,B,C <= 1001

第二行包括两个整数n,k, 0 <= n,k <= 30000000

输出

每组数据输出一行包括一个整数,代表第 k 大的数的大小。

样例输入

1
1 2 3
2 2

样例输出

1

提示

注意你的程序的运行效率,也就是所用的时间。

样例解释,生成两个数 1 和5, 第二大的数是1。

来源

[提交][状态][讨论版]