3430 . [模板題] Discrete Logarithm
TopCoder
Tags
Description
Each test case consist of $T$ cases.
Given $X, Y, M$. Print the minimum non-negative integer $K$ s.t. $X^ K \equiv Y (\bmod M)$, or $-1$ if there is no such $K$.
We note that $0^ 0 = 1$ in this problem.
Input Format
$T$
$X_ 0$ $Y_ 0$ $M_ 0$
$X_ 1$ $Y_ 1$ $M_ 1$
:
$X_ {T - 1}$ $Y_ {T - 1}$ $M_ {T - 1}$
Output Format
For each line, print answer.
Sample Input 1
7 2 1 5 4 7 10 8 6 10 5 2 11 5 9 11 0 0 1 0 2 4
Sample Output 1
0 -1 4 -1 4 0 -1
Hints
- $1 \leq T \leq 100$
- $0 \leq X, Y < M$
- $1 \leq M \leq 10^ 9$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|