結果

問題 No.3225 2×2行列相似判定 〜easy〜
コンテスト
ユーザー hitonanode
提出日時 2025-08-08 22:13:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 380 ms / 2,000 ms
コード長 862 bytes
コンパイル時間 621 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-08 22:14:55
合計ジャッジ時間 7,473 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <array>
#include <cassert>
#include <iostream>
using namespace std;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define REP(i, n) FOR(i, 0, n)

constexpr int P = 67;
using Mat = array<int, 4>;
Mat prod(const Mat &a, const Mat &b) {
    return {(a[0] * b[0] + a[1] * b[2]) % P, (a[0] * b[1] + a[1] * b[3]) % P,
            (a[2] * b[0] + a[3] * b[2]) % P, (a[2] * b[1] + a[3] * b[3]) % P};
}

int main() {
    Mat A, B, C;
    cin >> A[0] >> A[1] >> A[2] >> A[3];
    cin >> B[0] >> B[1] >> B[2] >> B[3];

    REP(i, P) REP(j, P) REP(k, P) REP(l, P) {
        C[0] = i, C[1] = j, C[2] = k, C[3] = l;
        auto det = (i * l - j * k) % P;
        if (det == 0) continue; // Not invertible
        if (prod(C, A) == prod(B, C)) {
            puts("Yes");
            return 0;
        }
    }

    puts("No");
}
0