結果

問題 No.3225 2×2行列相似判定 〜easy〜
コンテスト
ユーザー AP25
提出日時 2026-06-17 14:57:32
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,228 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,102 ms
コンパイル使用メモリ 170,444 KB
実行使用メモリ 11,296 KB
最終ジャッジ日時 2026-06-17 14:58:06
合計ジャッジ時間 4,863 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

using namespace std;

// 2x2の行列を表現するための型エイリアス
using Matrix = vector<vector<int>>;

// 行列の積を計算する関数
Matrix mul(const Matrix& a, const Matrix& b) {
    Matrix c(2, vector<int>(2, 0));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

// 2つの行列がmod 67で合同か判定する関数
bool func(const Matrix& a, const Matrix& b) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            // PythonとC++の負の数の剰余計算の挙動の違いを吸収
            int mod_a = ((a[i][j] % 67) + 67) % 67;
            int mod_b = ((b[i][j] % 67) + 67) % 67;
            if (mod_a != mod_b) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    // 入力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 行列Aの入力
    Matrix A(2, vector<int>(2));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            cin >> A[i][j];
        }
    }

    // 行列Bの入力
    Matrix B(2, vector<int>(2));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            cin >> B[i][j];
        }
    }

    // Pの各要素を全探索
    for (int p11 = 0; p11 < 67; ++p11) {
        for (int p12 = 0; p12 < 67; ++p12) {
            for (int p21 = 0; p21 < 67; ++p21) {
                for (int p22 = 0; p22 < 67; ++p22) {
                    // 行列式が0の場合はスキップ
                    if (p11 * p22 - p12 * p21 == 0) {
                        continue;
                    }
                    
                    Matrix P = {{p11, p12}, {p21, p22}};
                    Matrix PA = mul(P, A);
                    Matrix BP = mul(B, P);
                    
                    if (func(PA, BP)) {
                        cout << "Yes\n";
                        return 0; // Pythonのexit()に相当
                    }
                }
            }
        }
    }

    cout << "No\n";
    return 0;
}
0