No.3231 2×2行列相似判定 〜hard〜
タグ : / 解いたユーザー数 19
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
$p$ を素数 $10^9+7$ とします。整数 $a, b$ について、$a-b$ が $p$ で割り切れるとき、「$a, b$ は合同」と言い、$a \equiv b$ と書きます。行列 $A = (A_{i,j}), \, B = (B_{i, j})$ の各成分 $A_{i, j}, \, B_{i, j}$ が合同であるとき $A \equiv B$ と書きます。
整数を成分に持つ $2 \times 2$ 行列 $A, B$ が与えられます。このとき、整数を成分に持つ $2 \times 2$ 行列 $P = \begin{pmatrix}a & b \\ c & d\end{pmatrix}$ で、以下の2つの条件 :
- $ad - bc \not\equiv 0$
- $PA \equiv BP$
Yesを、存在しない場合Noを、それぞれ出力してください。
入力
$A_{1, 1} \ A_{1, 2}\\
A_{2, 1} \ A_{2, 2}\\
B_{1, 1} \ B_{1, 2}\\
B_{2, 1} \ B_{2, 2}$
$0 \leq A_{i, j}, B_{i, j} < p$ は整数です。
$A = \begin{pmatrix}A_{1, 1} \ A_{1, 2} \\ A_{2, 1} \ A_{2, 2}\end{pmatrix}, \ B = \begin{pmatrix}B_{1, 1} \ B_{1, 2} \\ B_{2, 1} \ B_{2, 2}\end{pmatrix}$ です。
出力
Yes または No を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3 1 3 102 999999865 69 999999911
出力
Yes
$P = \begin{pmatrix}3 & 13 \\ 2 & 9\end{pmatrix}$ とすると
$P \begin{pmatrix} 3 & 3 \\ 1 & 3 \end{pmatrix} \equiv \begin{pmatrix} 102 & -142 \\ 69 & -96\end{pmatrix} P$ となります。
${\rm mod} \, 1000000007$ では $-142 \equiv 999999865, \, -96 \equiv 999999911$ であることに注意してください。
サンプル2
入力
1 0 0 2 1 0 0 8
出力
No
固有値が異なるため、相似にはなりえません。
サンプル3
入力
0 1 0 0 0 0 0 0
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。