A2766. 随机数生成器
编程题
提高+/省选-
知识点
题目描述
小 W 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小 W 准备读一本新书，这本书一共有 $p$ 页，页码范围为 $0 \sim p-1$。
小 W 很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 ACGO上学习的线性同余法生成一个序列，来决定每天具体读哪一页。
我们用 $x_i$ 来表示通过这种方法生成出来的第 $i$ 个数，也即小 W 第 $i$ 天会读哪一页。这个方法需要设置 $3$ 个参数 $a,b,x_1$，满足 $0\leq a,b,x_1\lt p$，且 $a,b,x_1$ 都是整数。按照下面的公式生成出来一系列的整数：
$$x_{i+1} \equiv a \times x_i+b \pmod p$$
其中 $\bmod$ 表示取余操作。
但是这种方法可能导致某两天读的页码一样。
小 W 要读这本书的第 $t$ 页，所以他想知道最早在哪一天能读到第 $t$ 页，或者指出他永远不会读到第 $t$ 页。
小 W 很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 ACGO上学习的线性同余法生成一个序列，来决定每天具体读哪一页。
我们用 $x_i$ 来表示通过这种方法生成出来的第 $i$ 个数，也即小 W 第 $i$ 天会读哪一页。这个方法需要设置 $3$ 个参数 $a,b,x_1$，满足 $0\leq a,b,x_1\lt p$，且 $a,b,x_1$ 都是整数。按照下面的公式生成出来一系列的整数：
$$x_{i+1} \equiv a \times x_i+b \pmod p$$
其中 $\bmod$ 表示取余操作。
但是这种方法可能导致某两天读的页码一样。
小 W 要读这本书的第 $t$ 页，所以他想知道最早在哪一天能读到第 $t$ 页，或者指出他永远不会读到第 $t$ 页。
输入格式
**本题单测试点内有多组测试数据**。
第一行是一个整数 $T$，表示测试数据组数。
接下来 $T$ 行，每行有五个整数 $p, a, b, x_1, t$，表示一组数据。
第一行是一个整数 $T$，表示测试数据组数。
接下来 $T$ 行，每行有五个整数 $p, a, b, x_1, t$，表示一组数据。
输出格式
对于每组数据，输出一行一个整数表示他最早读到第 $t$ 页是哪一天。如果他永远不会读到第 $t$ 页，输出$-1$。
输入输出样例
输入 #1
3 7 1 1 3 3 7 2 2 2 0 7 2 2 2 1
输出 #1
1 3 -1
说明/提示
#### 数据规模与约定
对于全部的测试点，保证：
- $1 \leq T \leq 50$。
- $0 \leq a, b, x_1, t \lt p$，$2 \leq p \leq 10^9$。
- $p$ 为质数。
对于全部的测试点，保证：
- $1 \leq T \leq 50$。
- $0 \leq a, b, x_1, t \lt p$，$2 \leq p \leq 10^9$。
- $p$ 为质数。