P12540 [XJTUPC 2025] Discrete Logarithm

Given positive integers $a$, $c$, $p$, ensure that $p$ is $\textbf{prime}$, find $b$ such that: $$a^b \equiv b^c \pmod{p}$$ We say that integers $A, B, C$ have $A \equiv B \pmod{C}$ if and only if there exists an integer $k$ such that $A - B = C \times k$.

Input is just one line of three integers $a$, $c$, and $p$ ($1 \leq a, c < p \leq 10^9$), separated by a space, with the meaning as described in the question. The data guarantees that $p$ is a prime.

Output only one integer $b$ ($1 \leq b \leq 10^{18}$). If there are multiple legal answers, you can output any one. It can be proved that there is at least one solution in the range.

For the first sample, we have: $$3^{16} \equiv 16^5 \pmod{7}$$ Because: $$3^{16} \bmod 7 = 43046721 \bmod 7 = 4$$ $$16^5 \bmod 7 = 1048576 \bmod 7 = 4$$