P10030 "Cfz Round 3" Change

Given a prime number $p$ and three integers $a, b, c$, you need to perform operations on an integer $x$ that is initially $0$. In each operation, you may choose one of the following two types: - Type 1 operation: set $x$ to $(x \times a) \bmod p$. - Type 2 operation: set $x$ to $(x + b) \bmod p$. Here, $\bmod$ denotes the **modulo** operation. You need to determine whether it is possible to obtain $c$ after a **positive number of operations**. If possible, output `Yes`, otherwise output `No`. In this problem, the output is case-insensitive. That is, `yes`, `yeS`, `yEs`, `Yes`, `YEs`, `YeS`, `yES`, `Yes` are all considered `Yes`, and similarly for `No`.

**This problem contains multiple test cases.** The first line contains an integer $T$, representing the number of test cases. Then for each test case, one line contains four integers $p, a, b, c$.

For each test case, output one line: - If $c$ can be obtained after a positive number of operations, output `Yes`. - Otherwise, output `No`. In this problem, the output is case-insensitive. That is, `yes`, `yeS`, `yEs`, `Yes`, `YEs`, `YeS`, `yES`, `Yes` are all considered `Yes`, and similarly for `No`.

#### "Sample Explanation #1" For the $1$st test case, perform the Type 2 operation once and then perform the Type 1 operation twice. For the $2$nd test case, perform the Type 2 operation once and then perform the Type 1 operation once. For the $3$rd test case, it can be proven that no matter how you operate, you cannot obtain $3$. #### "Constraints" For all test cases, $1 \le T \le 100$, $0 \le a, b, c < p \le 10^9$. It is guaranteed that $p$ is prime. **You can get the score for this problem only if you pass all test points.** Translated by ChatGPT 5