/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
次の漸化式で定められる数列 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.
X_i=G となる i が存在するか判定し、存在するならばそのような最小の i を求めてください。
ここで、x \bmod y は、x を y で割ったあまり(最小非負剰余)を表すものとします。
1 ファイルにつき 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 行出力せよ。
t 行目には、\mathrm{case}_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
1 番目のケースについて、X=(1,3,2,0,\ldots) であることから、X_i=0 となる最小の i は 3 です。
2 番目のケースについて、X=(3,3,3,3,\ldots) であることから、X_i=0 となる i は存在しません。
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.