No.950 行列累乗

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 12
作問者 : chocoruskchocorusk / テスター : tempura_pptempura_pp
3 ProblemId : 3672 / 出題時の順位表
問題文最終更新日: 2019-12-11 15:15:17

問題文

整数を成分とする $2\times 2$ 行列 $A$, $B$ と素数 $p$ が与えられます。$A^n\equiv B \pmod p$ を満たす正の整数 $n$ が存在するか判定し、存在するなら最小値を求めてください。

入力

$p$
$A_{11}\ A_{12}$
$A_{21}\ A_{22}$
$B_{11}\ B_{12}$
$B_{21}\ B_{22}$

  • $2\leq p\leq 2\times 10^9$
  • $p$ は素数である。
  • $0\leq A_{ij}, B_{ij}\leq p-1$
  • 入力はすべて整数である。

出力

条件を満たす正の整数 $n$ が存在しないなら、$-1$ と出力せよ。存在するなら、$n$ としてありうる最小値を出力せよ。

サンプル

サンプル1
入力
5
4 4
4 1
1 1
1 4
出力
5

$\begin{pmatrix}4&4\\4&1\end{pmatrix}^5=\begin{pmatrix}9616&6676\\6676&4609\end{pmatrix}\equiv \begin{pmatrix}1&1\\1&4\end{pmatrix}\pmod 5$ です。

サンプル2
入力
7
3 2
4 5
0 6
1 2
出力
-1

サンプル3
入力
2
0 0
0 0
1 0
0 1
出力
-1

サンプル4
入力
1117117717
498588348 761212524
862899722 426122834
245821018 655774117
149233593 294448965
出力
334

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。