题目概述

给出矩阵 $A,B$ ，求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。

解题报告

哇 $A^x\equiv B(mod\ p)$ ，上BSGS！枚举 $A^{im}A^j\equiv B(mod\ p)$ ，然后检查 $A^j$ 中有没有出现过 $BA^{-im}$ 。

$A^{-im}$ ？矩阵求逆？我不会……填坑填坑：

可以证明下面三种操作相当于乘上了另一个矩阵：

1. 某一行（列）乘上一个数 $k$ 。
2. 交换两行（列）。
3. 把一行（列）加到另一行（列）上。

所以只要用高斯消元把 $A$ 消成单位矩阵，然后把消 $A$ 的方法全部用到一个单位矩阵 $I$ 上，$I$ 变成的矩阵 $C$ 就是 $A$ 的逆（只用上述三个操作相当于乘上了一个矩阵 $C$ ，那么 $A\times C=I,I\times C=C$ ）。

示例程序

注意虽然 $A$ 矩阵每次不需要整行扫过去，但 $B​$ 矩阵一定要整行扫过去。

#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=70;

int n,MOD;
struct Matrix{
    int s[maxn][maxn];inline void Zero() {for (int i=0;i<n;i++) for (int j=0;j<n;j++) s[i][j]=0;}
    inline void Unit() {Zero();for (int i=0;i<n;i++) s[i][i]=1;}
}A,B,INV;
inline bool operator < (const Matrix &a,const Matrix &b){
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (a.s[i][j]<b.s[i][j]) return true; else if (a.s[i][j]>b.s[i][j]) return false;
    return false;
}
map<Matrix,int> f;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline bool Inv(const Matrix &a,Matrix &B){
    static Matrix A;A=a;B.Unit();
    for (int i=0;i<n;i++){
        for (int j=i;j<n;j++)
            if (A.s[j][i]){
                for (int k=i;k<n;k++) swap(A.s[i][k],A.s[j][k]);
                for (int k=0;k<n;k++) swap(B.s[i][k],B.s[j][k]);break;
            }
        if (!A.s[i][i]) return false;
        for (int j=i+1;j<n;j++)
            while (A.s[j][i]){
                int t=A.s[j][i]/A.s[i][i];
                for (int k=i;k<n;k++) AMOD(A.s[j][k],MOD-(LL)t*A.s[i][k]%MOD);
                for (int k=0;k<n;k++) AMOD(B.s[j][k],MOD-(LL)t*B.s[i][k]%MOD);
                if (!A.s[j][i]) break;
                for (int k=i;k<n;k++) swap(A.s[j][k],A.s[i][k]);
                for (int k=0;k<n;k++) swap(B.s[j][k],B.s[i][k]);
            }
    }
    for (int i=n-1;~i;i--){
        int t=Pow(A.s[i][i],MOD-2);
        for (int k=i;k<n;k++) A.s[i][k]=(LL)A.s[i][k]*t%MOD;
        for (int k=0;k<n;k++) B.s[i][k]=(LL)B.s[i][k]*t%MOD;
        for (int j=0;j<i;j++)
            while (A.s[j][i]){
                int t=A.s[j][i]/A.s[i][i];
                for (int k=i;k<n;k++) AMOD(A.s[j][k],MOD-(LL)t*A.s[i][k]%MOD);
                for (int k=0;k<n;k++) AMOD(B.s[j][k],MOD-(LL)t*B.s[i][k]%MOD);
                if (!A.s[j][i]) break;
                for (int k=i;k<n;k++) swap(A.s[j][k],A.s[i][k]);
                for (int k=0;k<n;k++) swap(B.s[j][k],B.s[i][k]);
            }
    }
    return true;
}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.Zero();
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            for (int k=0;k<n;k++)
                AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);
    return c;
}
inline int BSGS(const Matrix &a,Matrix b){
    static Matrix Ba,INV;int m=sqrt(MOD)+1;Ba.Unit();f.clear();
    for (int i=0;i<m;i++,Ba=Ba*a) if (!f.count(Ba)) f[Ba]=i;Inv(Ba,INV);
    for (int i=0,j;i<m;i++,b=b*INV) if (f.count(b)) return i*m+f[b];return -1;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&MOD);
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) scanf("%d",&A.s[i][j]);
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) scanf("%d",&B.s[i][j]);
    printf("%d\n",BSGS(A,B));return 0;
}