AT_abc270_g [ABC270G] 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$ 行输出第 $t$ 组测试数据中，使 $X_i=G$ 的最小 $i$。如果不存在这样的 $i$，则输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

3
-1
10

说明/提示

限制条件

• $1 \leq T \leq 100$
• $2 \leq P \leq 10^9$
• $P$ 是质数
• $0 \leq A, B, S, G < P$
• 输入中的所有值均为整数

样例解释 1

对于第 $1$ 组数据，$X=(1,3,2,0,\ldots)$，因此最小的 $i$ 使 $X_i=0$ 是 $3$。
对于第 $2$ 组数据，$X=(3,3,3,3,\ldots)$，因此不存在 $i$ 使 $X_i=0$。

由 ChatGPT 4.1 翻译