自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:28:00，当前版本为作者最后更新于2021-01-03 09:39:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做这道题之前首先要明确一个重要的结论：嵌套形式的 $\gcd$ 的值等于原式中出现的数的 $\gcd$，比如说 $\gcd(a,\gcd(b,c))$ 就等于 $\gcd(a,b,c)$，$\gcd(\gcd(a,b),\gcd(b,c))$ 也等于 $\gcd(a,b,c)$。为什么呢？因为 $\gcd(a,b)$ 实际上是对 $a$ 和 $b$ 中每个质因数的指数取 $min$，如果出现的数始终是那几个，那无论怎么嵌套，每个质因数的指数的最小值都不会发生改变（关键点 $1$）。

再来看本题，我们会发现每一轮每个位置上的数都可以表达为$\gcd(S)$，$S$ 为整数集（关键点 $2$）。每进行一轮，每个位置上的 $S$ 里的所有元素便会“进入”相邻格子的集合。换句话说，每个位置上的 $S$ 每进行一轮就会扩大一圈（如果矩阵足够大的话实际上就是一个对角线长度不断增加 $2$ 的竖着的方形），这个过程其实就是从起点进行 bfs 的过程，边 bfs 边记录 gcd 即可，时间复杂度为 $O(nmlog(k))$（关键点 $3$）。

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=2e3+5;
int n,m,sx,sy,vis[N][N];
ll a[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

void bfs(){
	queue<int> qx,qy,qs;
	qx.push(sx),qy.push(sy),qs.push(0);
	vis[sx][sy]=1;
	ll sum=a[sx][sy];
	while(!qx.empty()){
		int x=qx.front(),y=qy.front(),s=qs.front();
		qx.pop(),qy.pop(),qs.pop();
		fo(i,0,3){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]) continue;
			vis[tx][ty]=1;
			qx.push(tx),qy.push(ty),qs.push(s+1);
			sum=__gcd(sum,a[tx][ty]);
			if(sum==1){
				cout<<s+1;
				return;
			}
		}
	}
	cout<<-1;
}

int main(){
	n=read(),m=read();
	fo(i,1,n) fo(j,1,m) a[i][j]=read();
	sx=read(),sy=read();
	if(a[sx][sy]==1){
		cout<<0;
		return 0;
	}
	bfs();
	return 0;
}

点个赞再走吧QAQ （关键点 $4$）