7127: ABC270 —— G - Sequence in mod P
[Creator : ]
Description
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.
$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.
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$
$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$.
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$.
Constraints
$1≤T≤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.
$2 \leq P \leq 10^9$
$P$ is a prime.
$0\leq A,B,S,G < P$
All values in the input are integers.
Sample 1 Input
3
5 2 1 1 0
5 2 2 3 0
11 1 1 0 10
Sample 1 Output
3
-1
10
For the first test case, we have $X=(1,3,2,0,\ldots)$, so the smallest ii such that $X_i=0$ is $3$.
For the second test case, we have $X=(3,3,3,3,\ldots)$, so there is no ii such that $X_i=0$.
For the second test case, we have $X=(3,3,3,3,\ldots)$, so there is no ii such that $X_i=0$.