結果

問題 No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
ユーザー 👑 Kazun
提出日時 2024-04-19 00:11:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,161 ms / 4,000 ms
コード長 2,026 bytes
コンパイル時間 403 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 281,600 KB
最終ジャッジ日時 2025-06-11 23:05:43
合計ジャッジ時間 29,222 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Matrix2:
    p = -1
    def __init__(self, a, b, c, d):
        p = Matrix2.p
        self.a = a % p
        self.b = b % p
        self.c = c % p
        self.d = d % p

    def __iter__(self):
        yield from (self.a, self.b, self.c, self.d)

    @classmethod
    def identity_matrix(cls):
        return cls(1, 0, 0, 1)

    def __mul__(self, other):
        p = Matrix2.p
        a1, b1, c1, d1 = self
        a2, b2, c2, d2 = other

        a = (a1 * a2 + b1 * c2) % p
        b = (a1 * b2 + b1 * d2) % p
        c = (c1 * a2 + d1 * c2) % p
        d = (c1 * b2 + d1 * d2) % p
        return Matrix2(a, b, c, d)

    def __pow__(self, k):
        A = self.identity_matrix()
        while k:
            if k & 1:
                A = A * self
            self = self * self
            k >>= 1
        return A

    def __eq__(self, other):
        return (self.a == other.a) and (self.b == other.b) and (self.c == other.c) and (self.d == other.d)

    def __hash__(self):
        return hash((self.a, self.b, self.c, self.d))

    def __repr__(self):
        return f'[[{self.a}, {self.b}], [{self.c}, {self.d}]]'

def input_matrix():
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    return Matrix2(a, b, c, d)

#==================================================
def solve():
    P = int(input())

    Matrix2.p = P

    A = input_matrix()
    B = input_matrix()

    E = set()
    y = B
    for _ in range(P):
        y = A * y
        E.add(y)

    step = pow(A, P)
    head = Matrix2.identity_matrix()
    count = 0
    for k in range(1, P + 1):
        tail = head
        head = step * head

        if head not in E:
            continue

        body = tail
        for n in range((k - 1) * P, k * P):
            if body == B:
                return n

            body = A * body

        count += 1
        if count == 2:
            break
    return -1

#==================================================
T = int(input())
print(*[solve() for _ in range(T)], sep = "\n")
0