結果

問題 No.3020 ユークリッドの互除法・改
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-02-09 01:07:41
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,371 bytes
コンパイル時間 2,500 ms
コンパイル使用メモリ 92,252 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-09 22:01:21
合計ジャッジ時間 3,583 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.array, std.conv, std.math, std.range, std.stdio, std.typecons;

struct Matrix {
	long
		a11, a12,
		a21, a22;
	
	void exchange_row() {
		swap(a11, a21), swap(a12, a22);
	}
	
	void exchange_column() {
		swap(a11, a12), swap(a21, a22);
	}
	
	void min_to11() {
		auto m = [a11, a12, a21, a22].filter!(a => a != 0).reduce!"min(a.abs, b.abs)";
		if (a21.abs == m) {
			exchange_row();
		}
		else if (a12.abs == m) {
			exchange_column();
		}
		else if (a22.abs == m) {
			exchange_row();
			exchange_column();
		}
		else assert(a11.abs == m);
		if (a11 < 0) a11 = -a11, a21 = -a21;
	}
	
	// true if set to smith form
	bool one_step() {
		min_to11();
		// row
		auto q1 = a21 / a11;
		a21 -= a11 * q1;
		a22 -= a12 * q1;
		// column
		auto q2 = a12 / a11;
		a12 -= a11 * q2;
		a22 -= a21 * q2;
		
		if (a12 == 0 && a21 == 0) {
			min_to11();
			auto b = a11;
			auto q = a22 / b;
			auto r = a22 % b;
			if (r == 0) {
				a22 = a22.abs;
				return true;
			}
			a11 = r,   a21 = -b,
			a12 = b*q, a22 = b ;
		}
		return false;
	}
	
	void to_smith_form() {
		if (a11 == 0 && a12 == 0 && a21 == 0 && a22 == 0) return;
		while (!one_step()) {}
	}
}

void main() {
	auto row1 = readln.split.to!(long[]);
	auto row2 = readln.split.to!(long[]);
	auto mat = Matrix(row1[0], row1[1], row2[0], row2[1]);
	mat.to_smith_form();
	writeln(mat.a11, " ", mat.a22);
}
0