102706: [AtCoder]ABC270 G - Sequence in mod P
Description
Score : $600$ points
Problem Statement
There is a sequence $X=(X_0, X_1, \ldots)$ defined by the following recurrence relation.
$X_i = \left\{ \begin{array}{ll} S & (i = 0)\\ (A X_{i-1}+B) \bmod P & (i \geq 1) \end{array} \right.$
Determine whether there is an $i$ such that $X_i=G$. If it exists, find the smallest such $i$.
Here, $x \bmod y$ denotes the remainder when $x$ is divided by $y$ (the least non-negative residue).
You are given $T$ test cases for each input file.
Constraints
- $1 \leq T \leq 100$
- $2 \leq P \leq 10^9$
- $P$ is a prime.
- $0\leq A,B,S,G < P$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is in the following format:
$P$ $A$ $B$ $S$ $G$
Output
Print $T$ lines.
The $t$-th line should contain the smallest $i$ such that $X_i=G$ for $\mathrm{case}_t$, or -1 if there is no such $i$.
Sample Input 1
3 5 2 1 1 0 5 2 2 3 0 11 1 1 0 10
Sample Output 1
3 -1 10
For the first test case, we have $X=(1,3,2,0,\ldots)$, so the smallest $i$ such that $X_i=0$ is $3$.
For the second test case, we have $X=(3,3,3,3,\ldots)$, so there is no $i$ such that $X_i=0$.
Input
题意翻译
对于某个无穷序列 $\{X\}$，构造如下： $$ X_i = \begin{cases} S & i=0 \\ (A\times X_{i-1}+B)\bmod P & i \geq 1 \end{cases} $$ 求最小的 $i$ 满足 $X_i=G$，没有输出 `-1`。 多组数据，记 $T$ 为数据组数，则有 $1\le T\le100$。 保证 $P$ 是质数，$2\le P\le10^9$。 保证 $0\le A,B,S,G< P$。Output
问题描述
定义一个序列$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$个测试用例。
约束
- $1 \leq T \leq 100$
- $2 \leq P \leq 10^9$
- $P$是质数。
- $0\leq A,B,S,G < P$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
每个测试用例的格式如下：
$P$ $A$ $B$ $S$ $G$
输出
打印$T$行。
对于$\mathrm{case}_t$，第$t$行应包含使得$X_i=G$的最小的$i$，如果没有这样的$i$，则输出-1。
样例输入 1
3 5 2 1 1 0 5 2 2 3 0 11 1 1 0 10
样例输出 1
3 -1 10
对于第一个测试用例，我们有$X=(1,3,2,0,\ldots)$，所以使得$X_i=0$的最小的$i$是$3$。
对于第二个测试用例，我们有$X=(3,3,3,3,\ldots)$，所以不存在使得$X_i=0$的$i$。