vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 P7243 【最大公约数】

posted on 2021-01-03 09:39:18 | under 题解 |

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