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