Hide
Problem B
Pohlig-Hellman
Languages
en
is
Implement the Pohlig-Hellman algorithm to solve $g^x \equiv h \pmod{p}$ for $x$.
Input
Input is three lines. The first line contains the prime $p$ where $3 \leq p < 2^{63}$ and each prime factor of $p-1$ are less than $2^{40}$. The second line contains the integer $g$ where $2 \leq g < p$ of order at least 2. The third line contains the integer $h$ where $0 \leq h < p$.
Output
Output one line with any valid solution $0 \leq x < p - 1$ or no solution if no solution exists.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 1 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
449 6 99 |
182 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 4 3 |
no solution |
