P3306 [SDOI2013] Random Number Generator

Xiao W likes reading, and especially enjoys reading "Jean-Christophe".

Recently, Xiao W plans to read a new book that has $p$ pages, with page numbers ranging from $0 \sim p-1$. Xiao W is busy, so he can read only one page per day. To make things a bit more interesting, he plans to use the linear congruential method he learned at NOI2012 to generate a sequence to decide which page to read each day. Let $x_i$ denote the $i$-th number generated by this method, i.e., the page Xiao W will read on day $i$. This method requires three parameters $a, b, x_1$, satisfying $0 \leq a, b, x_1 \lt p$, and $a, b, x_1$ are integers. A sequence of integers is generated according to the following formula: $$x_{i+1} \equiv a \times x_i + b \pmod p$$ Here, $\bmod$ denotes the remainder operation. However, this method may cause the same page number to be read on two different days. Xiao W wants to read page $t$ of this book, so he wants to know the earliest day on which he can read page $t$, or determine that he will never read page $t$.

This problem contains multiple test cases in a single test point. The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains five integers $p, a, b, x_1, t$, representing one test case.

For each test case, output one line with a single integer indicating the earliest day on which he reads page $t$. If he will never read page $t$, output $-1$.

#### Constraints - $1 \leq T \leq 50$. - $0 \leq a, b, x_1, t \lt p$, $2 \leq p \leq 10^9$. - $p$ is a prime. Translated by ChatGPT 5