問題一覧 >
通常問題
No.3020 ユークリッドの互除法・改
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 75
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑
p-adic
問題文最終更新日: 2025-02-15 12:40:38
問題文
成分が整数からなる2×2行列
(A11A21A12A22)
が入力から与えられます。この行列に対して、以下の操作(基本変形)を考えます。
- 行を入れ替える。
- 列を入れ替える。
- ある行を−1倍する。
- ある列を−1倍する。
- ある行に他方の行を整数倍したものを加える。
- ある列に他方の列を整数倍したものを加える。
この操作を繰り返すことで、以下のような行列(スミス標準形)にただ一通りに変形できることが知られています:
(D100D2)
ただし、D1,D2 は 0 以上の整数で、D1 は D2 を割り切ります。ここで、あらゆる整数 d は 0 を割り切り、0 は 0 だけを割り切ると解釈します。
このような D1,D2 をこの順に半角スペース一字で区切って出力してください。
大ヒント
上記の4種類の操作で、
- 行列式の絶対値 ∣A11A22−A12A21∣
- A11,A21,A12,A22 の最大公約数
は不変です。D1 は D2 を割り切るので、D1=gcd(D1,D2)=gcd(A11,A21,A12,A22) となり、D1D2=… (自分で考えてね)となります。
ただし、gcd(d,0)=∣d∣ です。
入力
A11 A12
A21 A22
−108≤Aij≤108.
サンプル
サンプル1
入力
3 0
0 5
出力
1 15
変形の一例を示す。
(3005)→(3−305)→(3−332)→(323−3)→(23−33)→(21−36)→(01−156)→(01−150)→(100−15)→(10015)
サンプル2
入力
12 34
56 78
出力
2 484
サンプル3
入力
100000000 0
0 99999999
出力
1 9999999900000000
32bit 整数値に収まらない可能性があることに注意。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。