No.3020 ユークリッドの互除法・改
タグ : / 解いたユーザー数 75
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
成分が整数からなる2×2行列
$\begin{pmatrix}
A_{11} & A_{12}\\
A_{21} & A_{22}
\end{pmatrix}$
が入力から与えられます。この行列に対して、以下の操作(基本変形)を考えます。
- 行を入れ替える。
- 列を入れ替える。
- ある行を$-1$倍する。
- ある列を$-1$倍する。
- ある行に他方の行を整数倍したものを加える。
- ある列に他方の列を整数倍したものを加える。
この操作を繰り返すことで、以下のような行列（スミス標準形）にただ一通りに変形できることが知られています:
$\begin{pmatrix}
D_1 & 0\\
0 & D_2\\
\end{pmatrix}$
ただし、$D_1, D_2$ は $0$ 以上の整数で、$D_1$ は $D_2$ を割り切ります。ここで、あらゆる整数 $d$ は $0$ を割り切り、$0$ は $0$ だけを割り切ると解釈します。
このような $D_1, D_2$ をこの順に半角スペース一字で区切って出力してください。
大ヒント
上記の4種類の操作で、- 行列式の絶対値 $|A_{11}A_{22} - A_{12}A_{21}|$
- $A_{11}, A_{21}, A_{12}, A_{22}$ の最大公約数
ただし、${\rm gcd}(d, 0) = |d|$ です。
入力
$A_{11} \ A_{12}$
$A_{21} \ A_{22}$
$-10^8 \leq A_{ij} \leq 10^8.$
出力
最後に改行してください。
サンプル
サンプル1
入力
3 0 0 5
出力
1 15
変形の一例を示す。
$\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}$
サンプル2
入力
12 34 56 78
出力
2 484
サンプル3
入力
100000000 0 0 99999999
出力
1 9999999900000000
32bit 整数値に収まらない可能性があることに注意。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。