Discrete Logarithm

AC一覧

Problem Statement (Japanese) / 問題文 (日本語)

この問題は $T$ ケース与えられる。

$X, Y, M$ が与えられる。$X^K \equiv Y (\bmod M)$ なる非負整数 $K$ のうち、最小を答えよ(存在しない場合は-1)。

なお、$0^0 = 1$ とします。

Constraints / 制約

Input / 入力

$T$
$X_0$ $Y_0$ $M_0$
$X_1$ $Y_1$ $M_1$
:
$X_{T - 1}$ $Y_{T - 1}$ $M_{T - 1}$

Output / 出力

各行に各ケースの答えを出力

Sample / サンプル

# 1

7
2 1 5
4 7 10
8 6 10
5 2 11
5 9 11
0 0 1
0 2 4
0
-1
4
-1
4
0
-1

Forum


Timelimit: 10 secs