Bài tập | NEU OJ

Cho ma trận vuông $A$ cấp $n$ với các phần tử nguyên trong $[0,p-1]$ , $p$ nguyên tố. Cấp (order) của $A$ theo modulo $p$ là số nguyên dương $k$ nhỏ nhất sao cho $A^{k}\equiv I\pmod p$ ( $I$ là ma trận đơn vị). Cho $A$ , $p$ và giới hạn trên $M$ , tìm $k$ nhỏ nhất trong đoạn $[1,M]$ sao cho $A^{k}\equiv I\pmod p$ ; nếu không tồn tại $k$ nào trong đoạn đó, in $-1$ .

Định dạng đầu vào:
Dòng 1: ba số nguyên $n\ p\ M$ . $n$ dòng tiếp theo là ma trận $A$ (mỗi phần tử trong $[0,p-1]$ ).
Ràng buộc đầu vào:
$1 \le n \le 3$ , $p$ nguyên tố, $2 \le p \le 50$ , $1 \le M \le 10000$ .
Định dạng đầu ra:
In ra cấp $k$ nhỏ nhất trong $[1,M]$ sao cho $A^{k}\equiv I\pmod p$ , hoặc $-1$ nếu không tồn tại.

solution

Đề bài: [Toán cho CNTT] Tìm cấp của ma trận theo modulo