题解 P7243 【最大公约数】

· · 题解

首先发现当所有数的 \gcd\not=1 时无解，然后想到直接模拟，期望得分 45pts

再看到 Subtask 6，发现 a_{i,j} \leq 2，容易发现是求离 (x,y) 最近的 1 的曼哈顿距离

for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(a[i][j]==1)ans=min(ans,abs(i-X)+abs(j-Y));

发现有解时，变换一遍之后 a 中至少有一个 1 （读者自行思考）

那么先变换一遍，然后求答案同上

for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j){ll G1=gcd(a[i-1][j],a[i][j-1]),G2=gcd(a[i+1][j],a[i][j+1]),G3=gcd(G1,G2);b[i][j]=gcd(a[i][j],G3);}
for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)if(b[i][j]==1)sum=min(sum,abs(i-X)+abs(j-Y)+(a[i][j]!=1));

但是这样会超时，因为时间复杂度是 O(nm\times5\log1e18)，会超时

再想一下，发现只要求离 (x,y) 最近的那个 1 就行了

容易想到从 (x,y) bfs 一遍

最坏的时间复杂度还是 O(nm\times5\log1e18)，但在这里跑不满应该能被卡掉？

\text {Code} 
#include<bits/stdc++.h>
using namespace std;
inline long long gcd(long long a,long long b){long long r;while(b)r=a%b,a=b,b=r;return a;}
const int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
long long a[2005][2005],G;
struct Node{int x,y;}t;
bool vis[2005][2005];
queue<Node>q;
int n,m,X,Y;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%lld",&a[i][j]),G=gcd(G,a[i][j]);
    if(G!=1){printf("-1");return 0;}
    scanf("%d%d",&X,&Y),q.push(Node{X,Y}),vis[X][Y]=true;
    while(!q.empty()){
        t=q.front(),q.pop(),G=gcd(a[t.x][t.y],gcd(gcd(a[t.x-1][t.y],a[t.x][t.y-1]),gcd(a[t.x+1][t.y],a[t.x][t.y+1])));
        if(G==1){printf("%d",abs(t.x-X)+abs(t.y-Y)+(a[t.x][t.y]!=1));return 0;}
        for(int i=0;i<4;++i){int nx=t.x+dx[i],ny=t.y+dy[i];if(nx>0&&nx<=n&&ny>0&&ny<=m&&!vis[nx][ny])vis[nx][ny]=true,q.push(Node{nx,ny});}
    }
}