No.3231 2×2 Matrix Similarity Testing ~hard~
タグ : / 解いたユーザー数 19
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
Problem Statement
Let $p$ be the prime $10^9+7$. For integers $a, b$, if $a-b$ is divisible by $p$, we say that "$a, b$ are congruent" and write $a \equiv b$. For matrices $A = (A_{i,j}), \, B = (B_{i, j})$, if the entries $A_{i, j}, \, B_{i, j}$ are congruent for every position, we write $A \equiv B$.
You are given $2 \times 2$ matrices $A, B$ with integer entries. Does there exist a $2 \times 2$ matrix $P = \begin{pmatrix}a & b \\ c & d\end{pmatrix}$ with integer entries satisfying both of the following conditions:
- $ad - bc \not\equiv 0$
- $PA \equiv BP$
Yes if such a matrix exists, and No if it does not.
Input
$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$ are integers.
$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}$.
Output
Print Yes or No.
Print a newline at the end.
Sample
Sample 1
Input
3 3 1 3 102 999999865 69 999999911
Output
Yes
Taking $P = \begin{pmatrix}3 & 13 \\ 2 & 9\end{pmatrix}$, we have
$P \begin{pmatrix} 3 & 3 \\ 1 & 3 \end{pmatrix} \equiv \begin{pmatrix} 102 & -142 \\ 69 & -96\end{pmatrix} P$.
Note that $-142 \equiv 999999865, \, -96 \equiv 999999911$ in ${\rm mod} \, 1000000007$.
Sample 2
Input
1 0 0 2 1 0 0 8
Output
No
The eigenvalues differ, so the matrices cannot be similar.
Sample 3
Input
0 1 0 0 0 0 0 0
Output
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。