Discrete Logarithm#4318
Given natural numbers , , and , your task is to determine the discrete logarithm of with base modulo . Specifically, you need to find a number (0 \le x < n) such that a^x \equiv b \pmod{n}.
The input consists of a single line containing three integers , , and , separated by spaces (0 \le a, b, n \le 10^{12}), with the condition that n \neq 0.
Output on the first line if the discrete logarithm does not exist. Otherwise, print the value of the discrete logarithm. If there are multiple possible answers, any one of them can be printed.
Example 1