题解 P7243 【最大公约数】

· · 题解

做这道题之前首先要明确一个重要的结论：嵌套形式的 \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）