← 返回题目列表

AtCoder · abc270_g

G. mod P 中的序列

中文机器翻译题面 查看原题

分数: 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.

判断是否存在 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 行。
的 t- 第行应包含最小的 i 这样 X_i=G 为 \mathrm{case}_t,或 -1 如果没有这样的 i.


示例输入 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),所以最小 i 这样 X_i=0 is 3.
对于第二个测试用例,我们有 X=(3,3,3,3,\ldots),所以没有 i 这样 X_i=0.