文件详细信息

下载本文件

本文件的大小为 2193 字节。

/*
## 题目大意

给定矩阵 $A$、$B$ 和模数 $p$，求最小的 $x$ 满足 $A^x \equiv B \pmod p$。

保证 $n \le 70$，$p \le 19997$，$p$ 为质数，$0 \le A_{i,j},B_{i,j}<p$，$A$ 有逆。数据保证在 $p$ 内有解。

## 做法 1

使用 BSGS 算法，设 $m=\lfloor \sqrt p \rfloor+1$，$x=im-j$，那么就有 $(A^m)^i \equiv A^jB \pmod p$，时间复杂度为 $O(n^3 \sqrt p)$。
*/
#include<chrono>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/assoc_container.hpp>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef unsigned int uint;
typedef unsigned long long ull;
const uint maxn=70;
const ull P=998244353;
uint n,p,m;
struct Matrix{
	uint v[maxn][maxn];
	Matrix(){
		memset(v,0,sizeof(v));
	}
}A,B,init;
Matrix operator*(const Matrix a,const Matrix b){
	Matrix ans;
	for(uint i=0;i<n;i++)
		for(uint j=0;j<n;j++)
			for(uint k=0;k<n;k++)
				ans.v[i][j]=(ans.v[i][j]+a.v[i][k]*b.v[k][j])%p;
	return ans;
}
Matrix qpow(Matrix a,uint x){
	Matrix ans=init;
	while(x){
		if(x&1)ans=ans*a;
		a=a*a;
		x>>=1;
	}
	return ans;
}
bool operator==(const Matrix a,const Matrix b){
	for(uint i=0;i<n;i++)
		for(uint j=0;j<n;j++)
			if(a.v[i][j]!=b.v[i][j])
				return false;
	return true;
}
struct custom_hash{
	uint operator()(const Matrix a)const{
		uint hash=0;
		for(uint i=0;i<n;i++)
			for(uint j=0;j<n;j++)
				hash=hash*p+a.v[i][j];
		return hash;
	}
};
__gnu_pbds::gp_hash_table<Matrix,uint,custom_hash>map;
int main(){
	read(n),read(p);
	for(uint i=0;i<n;i++)init.v[i][i]=1;
	for(uint i=0;i<n;i++)
		for(uint j=0;j<n;j++)
			read(A.v[i][j]);
	for(uint i=0;i<n;i++)
		for(uint j=0;j<n;j++)
			read(B.v[i][j]);
	m=uint(sqrt(p))+1;
	Matrix now=B,step;
	for(uint i=0;i<=m;i++){
		map[now]=i;
		now=now*A;
	}
	now=step=qpow(A,m);
	for(uint i=1;i<=m;i++){
		if(map.find(now)!=map.end()){
			write(i*m-map[now]),putchar('\n');
			break;
		}
		now=now*step;
	}
	return 0;
}