P7611 [THUPC 2021] Lucky Positions

Little Z is a lively and active child. One day, she stands at position $b$ on the number line and is ready to start moving along the positive direction of the number line. Each time Little Z takes one step, she immediately moves forward by $a$ units along the positive direction. Interestingly, $a$ and $b$ are both positive integers, so at any moment, the position where Little Z stands is also a positive integer. Little Z’s lucky number is a positive integer $c$. Little Z believes that if the position she moves to is coprime with $c$, then that position is a lucky position. Please help Little Z determine whether she can move to a lucky position; if she can, compute any number of steps $n$ such that she can move to a lucky position. Concise statement: Given three positive integers $a,b,c$, determine whether there exists a non-negative integer $n$ such that $(an+b, c)=1$. If it exists, output any one solution, where $(\cdot, \cdot)$ denotes the greatest common divisor.

The first line contains a positive integer $T$, indicating the number of test cases. Then each test case is given in order. For each test case, the input is one line with three positive integers $a,b,c$, with meanings as described above. For all input, $1\le T\le 10$, $1\le a,b,c < 10^{2000}$. All input numbers are given in decimal.

For each test case, output one integer per line. If no valid number of steps $n$ can be found, output `-1`. Otherwise, output a non-negative integer representing a valid number of steps $n$. All outputs should be in decimal. The length of each output line must not exceed $2000$. The testdata guarantees that a solution within the output length limit exists. Also, do not output extra spaces or any extra characters, and make sure there is a newline at the end of the output; otherwise, it may affect the judging.

**Sample Explanation** For the first test case, $a=1,b=2,c=3$. Here $b$ and $c$ are already coprime, so $n=0$ is a solution. For the second test case, $a=1,b=3,c=6$. Taking $n=2$, we have $an+b=5$, which is coprime with $6$, so it is a solution. For the third test case, $a=2,b=2,c=2$. Then $an+b=2n+2$, and for any $n$ we have $(an+b,c)=2$, so such an $n$ does not exist, and we output `-1`. **Source** From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021). Resources such as the editorial can be found at [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master). Translated by ChatGPT 5