問題一覧 > 通常問題

No.950 行列累乗

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : chocorusk / テスター : tempura_pp
5 ProblemId : 3672 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-11 15:15:17

問題文

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

入力

p
A11 A12
A21 A22
B11 B12
B21 B22

  • 2p2×109
  • p は素数である。
  • 0Aij,Bijp1
  • 入力はすべて整数である。

出力

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

サンプル

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

(4441)5=(9616667666764609)(1114)(mod5) です。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。