問題一覧 > 通常問題

No.3020 Euclidean Algorithm, Revised

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 73
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11920 / 自分の提出
問題文最終更新日: 2025-02-15 12:40:38
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 456 オムニバス (順位表) の他の問題:

Problem Statement

A 2×2 matrix with integer entries

$\begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}$

is given as input. Consider the following operations (elementary transformations) on this matrix.

  • Swap the rows.
  • Swap the columns.
  • Multiply a row by $-1$.
  • Multiply a column by $-1$.
  • Add an integer multiple of the other row to a row.
  • Add an integer multiple of the other column to a column.

It is known that by repeating these operations, the matrix can be transformed into a unique matrix of the following form (the Smith normal form):

$\begin{pmatrix} D_1 & 0\\ 0 & D_2\\ \end{pmatrix}$

Here, $D_1, D_2$ are integers greater than or equal to $0$, and $D_1$ divides $D_2$. We interpret this so that every integer $d$ divides $0$, and $0$ divides only $0$.
Print such $D_1, D_2$ in this order, separated by a single half-width space.

Big Hint Under the above 4 types of operations, the following
  • the absolute value of the determinant $|A_{11}A_{22} - A_{12}A_{21}|$
  • the greatest common divisor of $A_{11}, A_{21}, A_{12}, A_{22}$
are invariant. Since $D_1$ divides $D_2$, we have $D_1 = {\rm gcd}(D_1, D_2) = {\rm gcd}(A_{11}, A_{21}, A_{12}, A_{22})$, and $D_1 D_2 = \dots$ (figure this out yourself).
Note that ${\rm gcd}(d, 0) = |d|$.

Input

$A_{11} \ A_{12}$
$A_{21} \ A_{22}$

$-10^8 \leq A_{ij} \leq 10^8.$

Output

Print a newline at the end.

Sample

Sample 1
Input
3 0
0 5
Output
1 15

An example of the transformation is shown below.
$\begin{pmatrix}3 & 0 \\ 0 & 5\end{pmatrix} \rightarrow \begin{pmatrix}3 & 0 \\ -3 & 5\end{pmatrix} \rightarrow \begin{pmatrix}3 & 3 \\ -3 & 2\end{pmatrix} \rightarrow \begin{pmatrix}3 & 3 \\ 2 & -3\end{pmatrix} \rightarrow \begin{pmatrix}2 & -3 \\ 3 & 3\end{pmatrix} \rightarrow \begin{pmatrix}2 & -3 \\ 1 & 6\end{pmatrix} \rightarrow \begin{pmatrix}0 & -15 \\ 1 & 6\end{pmatrix} \rightarrow \begin{pmatrix}0 & -15 \\ 1 & 0\end{pmatrix} \rightarrow \begin{pmatrix}1 & 0 \\ 0 & -15\end{pmatrix} \rightarrow \begin{pmatrix}1 & 0 \\ 0 & 15\end{pmatrix}$

Sample 2
Input
12 34
56 78
Output
2 484

Sample 3
Input
100000000 0
0 99999999
Output
1 9999999900000000

Note that the values may not fit in a 32-bit integer.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。