結果

問題 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0