問題一覧 > 通常問題

No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 12
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 4789 / 自分の提出
問題文最終更新日: 2025-05-30 00:51:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~ (順位表) の他の問題:

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