题目描述
给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p)
输入
第一行两个整数n和p，表示矩阵的阶和模数,接下来一个n * n的矩阵A.接下来一个n * n的矩阵B
输出
输出一个正整数，表示最小的可能的x，数据保证在p内有解
样例输入
2 7
1 1
1 0
5 3
3 2
1 1
1 0
5 3
3 2
样例输出
4
提示
对于100%的数据，n <= 70,p <=19997，p为质数,0<= A_{ij},B_{ij}< p
保证A有逆
发现式子的形式可以$BSGS$，但唯一不同的就是把数换成了矩阵。我们知道，正常的$BSGS$有两种形式：$a^{i*m+j}\equiv b(mod\ p)$和$a^{i*m-j}\equiv b(mod\ p)$。第一种形式需要求逆，而第二种不需要。那么我们可以用第二种方法来求以避免矩阵求逆。至于如何快速判两个矩阵相同可以使用$hash$来判，为了防止被卡建议使用两个$base$。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define pr pair<ull,ull>
using namespace std;
int base1=10007;
int base2=233;
int n,p,m;
map<pr,int>mp;
struct lty
{
ull v[80][80],val1,val2;
lty(int x)
{
memset(v,0,sizeof(v));
val1=val2=0;
for(int i=1;i<=n;i++)
{
v[i][i]=x;
}
}
lty operator *(lty a)
{
lty ans(0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
ans.v[i][j]=(ans.v[i][j]+v[i][k]*a.v[k][j])%p;
}
}
}
return ans;
}
void hash()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
val1=val1*base1+v[i][j];
val2=val2*base2+v[i][j];
}
}
}
};
int main()
{
scanf("%d%d",&n,&p);
m=ceil(sqrt(p));
lty A(0),B(0),C(1),D(1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%llu",&A.v[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%llu",&B.v[i][j]);
}
}
for(int i=1;i<=m;i++)
{
B=B*A;
B.hash();
mp[make_pair(B.val1,B.val2)]=i;
}
for(int i=1;i<=m;i++)
{
C=C*A;
}
for(int i=1;i<=m;i++)
{
D=D*C;
D.hash();
if(mp.find(make_pair(D.val1,D.val2))!=mp.end())
{
printf("%d",i*m-mp[make_pair(D.val1,D.val2)]);
return 0;
}
}
}