P5605 Little A and Two Immortals

Little A is an ordinary high school student, but one day he was suddenly dragged into a game of immortals. Please help him!

One day, Little A was walking home after school when he suddenly met two immortal dream-makers, Zaomengzhe and Jeremy. As soon as they saw Little A, they said they wanted to play a game with him. Little A was covered in golden light and, for some reason, agreed to their request. The rules of the game are as follows: the two immortals first choose a positive integer $m$, and guarantee that $m$ is a positive integer power of an odd prime $p$. Then they play $n$ rounds. In each round, Zaomengzhe chooses a positive integer $x$, and Jeremy chooses a positive integer $y$, with $(x, m) = 1$ and $(y, m) = 1$, meaning $x$ is coprime to $m$ and $y$ is coprime to $m$. Then they ask Little A whether there exists a non-negative integer $a$ such that $x^a \equiv y \pmod{m}$. The immortals say that only if Little A answers correctly in every round can he return to normal life. With no other choice, he asks you, the smart one, for help.

The first line contains two positive integers $m, n$. The next $n$ lines each contain two positive integers $x, y$.

Output a total of $n$ lines, each corresponding to Little A's answer for one round. If it exists, output `Yes`; otherwise, output `No`.

**Sample Explanation** $1^a \equiv 1 \not \equiv 4 \pmod {9}$. $2^6 \equiv 64 \equiv 1 \pmod {9}$. $7^2 \equiv 49 \equiv 4 \pmod {9}$. **Constraints** This problem has $7$ subtasks. You must pass all test points within a subtask to obtain the score for that subtask. For all testdata, $1\le n\le 2\times 10^4$, $3\le m \le 10^{18}$, $1 \le x, y < m$. | # | Score | $n$ | $m$ | Special Property 1 | Time Limit | | ---- | ---- | ------------------------ | ------------------- | --------- | --------- | | 1 | 3 | $\le 5$ | $\le 10^6$ | × | 1s | | 2 | 37 | $\le 5$ | $\le 10^9$ | × | 1s | | 3 | 22 | $= 1$ | $\le 10^{18}$ | × | 1s | | 4 | 13 | $\le 100$ | $\le 10^{18}$ | √ | 1s | | 5 | 10 | $\le 100$ | $\le 10^{18}$ | × | 1s | | 6 | 5 | $\le 2000$ | $\le 10^{18}$ | × | 1s | | 7 | 10 | $\le 2\times 10^4$ | $\le 10^{18}$ | × | 3s | Special Property 1: Let $m = p^{a}$. Then $p$ is a prime chosen uniformly at random from $[3, 10^{18}]$. **Hint** You may use `__int128`. Translated by ChatGPT 5