結果
問題 |
No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
|
ユーザー |
👑 ![]() |
提出日時 | 2024-01-28 23:55:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,146 ms / 4,000 ms |
コード長 | 2,202 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 283,320 KB |
最終ジャッジ日時 | 2025-06-11 23:04:52 |
合計ジャッジ時間 | 31,768 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
from dataclasses import dataclass @dataclass class Matrix2: p = -1 def __init__(self, a: int, b: int, c: int, d: int): 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) -> "Matrix2": return cls(1, 0, 0, 1) def __mul__(self, other: "Matrix2") -> "Matrix2": 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: int) -> "Matrix2": A = self.__class__.identity_matrix() while k: if k & 1: A = A * self self = self * self k >>= 1 return A def __eq__(self, other: "Matrix2") -> "Matrix2": return (self.a == other.a) and (self.b == other.b) and (self.c == other.c) and (self.d == other.d) def __hash__(self) -> int: return hash((self.a, self.b, self.c, self.d)) def __repr__(self): return f"Matrix2({self.a}, {self.b}, {self.c}, {self.d})" def input_matrix() -> Matrix2: 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")