No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
Problem Visual
▶ Open to reveal the problem visual
Introduction
The bird, released from all the pressure, casts off the feathers it wore and flies away...
Problem Statement
Let $P$ be a prime number.
You are given square matrices of order $2$ with integer entries, $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}$. Does there exist a non-negative integer $N$ such that $$A^N \equiv B \pmod{P}$$ ? If one exists, find the smallest such non-negative integer $N$.
Here, $A^0$ is defined to be the identity matrix of order $2$.
Solve $T$ test cases.
Notes
For $2$ square matrices of order $2$ with integer entries, $X=\begin{pmatrix} X_{1,1} & X_{1,2} \\ X_{2,1} & X_{2,2} \end{pmatrix}, Y=\begin{pmatrix} Y_{1,1} & Y_{1,2} \\ Y_{2,1} & Y_{2,2} \end{pmatrix}$, we write $X \equiv Y \pmod{P}$ if and only if all of $$X_{1,1} \equiv Y_{1,1} \pmod{P}, \quad X_{1,2} \equiv Y_{1,2} \pmod{P}, \quad X_{2,1} \equiv Y_{2,1} \pmod{P}, \quad X_{2,2} \equiv Y_{2,2} \pmod{P}$$ hold.
Under the constraints of this problem, it can be proved that for any non-negative integer $N$, $A^N$ is a square matrix of order $2$ with integer entries.
Constraints
- $1 \leq T \leq 5$.
- Constraints for each test case
- $2 \leq P \leq 3 \times 10^5$
- $P$ is a prime number.
- $0 \leq A_{i,j} \lt P \quad (i \in \{1,2\}, j \in \{1,2\})$
- $0 \leq B_{i,j} \lt P \quad (i \in \{1,2\}, j \in \{1,2\})$
- All input values are integers.
Input
$T$
$\mathrm{Testcase}_1$
$\mathrm{Testcase}_2$
$\vdots$
$\mathrm{Testcase}_T$
Each test case is given in the following format.
$P$
$A_{1,1}$ $A_{1,2}$
$A_{2,1}$ $A_{2,2}$
$B_{1,1}$ $B_{1,2}$
$B_{2,1}$ $B_{2,2}$
Output
The output consists of $T$ lines.
On the $t~(1 \leq t \leq T)$-th line, if there exists a non-negative integer $N$ such that $A^N \equiv B \pmod{P}$, print the smallest such non-negative integer $N$; otherwise, print -1.
Do not forget the newline at the end.
Sample
Sample 1
Input
3 97 1 3 2 2 25 39 26 38 2 1 0 0 1 0 0 0 0 3 2 0 0 0 1 0 0 0
Output
3 -1 2
- [Test case $1$] We have $A = \begin{pmatrix} 1 & 3 \\ 2 & 2 \end{pmatrix}, B = \begin{pmatrix} 25 & 39 \\ 26 & 38 \end{pmatrix}$. $$A^0 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad A^1 = \begin{pmatrix} 1 & 3 \\ 2 & 2 \end{pmatrix}, \quad A^2 = \begin{pmatrix} 7 & 9 \\ 6 & 10 \end{pmatrix},\quad A^3 = \begin{pmatrix} 25 & 39 \\ 26 & 38 \end{pmatrix}$$ Thus, $A^0, A^1, A^2 \not \equiv B \pmod{97}, A^3 \equiv B \pmod{97}$. Therefore, the answer is $N=3$.
- [Test case $2$] For any non-negative integer $N$, we have $A^N = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, so $A^N \not \equiv B \pmod{2}$. Therefore, you must print
-1. - [Test case $3$] Note that although $A^2 \neq B$, we have $A^2 \equiv B \pmod{3}$.
Sample 2
Input
2 200003 162435 193492 172878 37660 178621 199780 199289 135336 299993 10896 279378 226758 289189 16396 219907 249049 89986
Output
20150821 20240201
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun