Sequence in mod P

题目描述

有一个数列 $X=(X_0, X_1, \ldots)$，由如下递推关系定义。 $X_i = \left\{ \begin{array}{ll} S & (i = 0)\\ (A X_{i-1}+B) \bmod P & (i \geq 1) \end{array} \right.$ 判断是否存在某个 $i$ 使得 $X_i=G$。若存在，找出最小的这样的 $i$。
这里，$x \bmod y$ 表示将 $x$ 除以 $y$ 的余数（最小的非负剩余）。 对于每个输入文件给出 $T$ 个测试用例。

输入格式

输入从标准输入给出，格式如下： $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每个测试用例的格式如下： $P$ $A$ $B$ $S$ $G$

输出格式

输出 $T$ 行。
第 $t$ 行应包含对于 $\mathrm{case}_t$ 的最小的使 $X_i=G$ 的 $i$，若不存在则输出 $-1$。

3
5 2 1 1 0
5 2 2 3 0
11 1 1 0 10

3
-1
10

提示

$1 \leq T \leq 100$ $2 \leq P \leq 10^9$ $P$ 是素数。 0\leq A,B,S,G < P 输入中的所有数值均为整数。对于第一个测试用例，我们有 $X=(1,3,2,0,\ldots)$，因此使 $X_i=0$ 的最小 $i$ 是 $3$。
对于第二个测试用例，我们有 $X=(3,3,3,3,\ldots)$，因此不存在使 $X_i=0$ 的 $i$。

标签: AtCoder|abc270G

来源

AtCoder|abc270G