問題一覧 > 通常問題

No.3020 ユークリッドの互除法・改

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
1 ProblemId : 11920 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-15 12:40:38

問題文

成分が整数からなる2×2行列

(A11A12A21A22)\begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}

が入力から与えられます。この行列に対して、以下の操作(基本変形)を考えます。

  • 行を入れ替える。
  • 列を入れ替える。
  • ある行を−1-1倍する。
  • ある列を−1-1倍する。
  • ある行に他方の行を整数倍したものを加える。
  • ある列に他方の列を整数倍したものを加える。

この操作を繰り返すことで、以下のような行列（スミス標準形）にただ一通りに変形できることが知られています:

(D100D2)\begin{pmatrix} D_1 & 0\\ 0 & D_2\\ \end{pmatrix}

ただし、D1,D2D_1, D_2 は 00 以上の整数で、D1D_1 は D2D_2 を割り切ります。ここで、あらゆる整数 dd は 00 を割り切り、00 は 00 だけを割り切ると解釈します。
このような D1,D2D_1, D_2 をこの順に半角スペース一字で区切って出力してください。

大ヒント 上記の4種類の操作で、
  • 行列式の絶対値 ∣A11A22−A12A21∣|A_{11}A_{22} - A_{12}A_{21}|
  • A11,A21,A12,A22A_{11}, A_{21}, A_{12}, A_{22} の最大公約数
は不変です。D1D_1 は D2D_2 を割り切るので、D1=gcd(D1,D2)=gcd(A11,A21,A12,A22)D_1 = {\rm gcd}(D_1, D_2) = {\rm gcd}(A_{11}, A_{21}, A_{12}, A_{22}) となり、D1D2=…D_1 D_2 = \dots （自分で考えてね）となります。
ただし、gcd(d,0)=∣d∣{\rm gcd}(d, 0) = |d| です。

入力

A11 A12A_{11} \ A_{12}
A21 A22A_{21} \ A_{22}

−108≤Aij≤108.-10^8 \leq A_{ij} \leq 10^8.

出力

最後に改行してください。

サンプル

サンプル1
入力
3 0
0 5
出力
1 15

変形の一例を示す。
(3005)→(30−35)→(33−32)→(332−3)→(2−333)→(2−316)→(0−1516)→(0−1510)→(100−15)→(10015)\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もしくは右上の雲マークをクリックしてアカウントを作成してください。