No.950 行列累乗
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 :
chocorusk
/ テスター :
tempura_pp
タグ : / 解いたユーザー数 14
作問者 :
chocorusk
/ テスター :
tempura_pp
問題文最終更新日: 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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。