洛谷 P7243 最大公约数

题目链接

分析

根据 $\gcd$ 性质 $\gcd (a,\gcd (b,\gcd (c,d)))$ 就等于 $\gcd (a,b,c,d)$。

我们发现如果当前这层和前面的状态不互质的话，就会转移出下一层，而下一层只会往更深层转移，所以有拓扑序，可用广搜实现，从起点开始广搜，逐层扩散知道 $\gcd$ 为 1，求 $\gcd$ 时可用前面说的性质，分别来求。

代码

#include <bits/stdc++.h>
#define debug puts("Y")
#define int long long

using namespace std;

const int N = 2 * 1e3 + 5, kD[][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int n, m, h = 1, t, G, x, y, a[N][N], vis[N][N];

struct E {
	int x, y, S;
}q[N * N];

void Record (int x, int y, int step) {
	if (x < 1 || y < 1 || x > n || y > m || vis[x][y]) {
		return ;
	}
	vis[x][y] = 1, G = __gcd(G, a[x][y]);
	q[++ t] = {x, y, step};
	if(G == 1){
		cout << step;
		exit( 0 );
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
		}
	}
	cin >> x >> y;
	G = a[x][y];
	for (Record(x, y, 0); h <= t; h ++) {
		for(int i = 0; i < 4; i ++){
			Record(q[h].x + kD[i][0], q[h].y + kD[i][1], q[h].S + 1);
		}
	}
	cout << -1;
  return 0;
}