题解：P7243 最大公约数

对于 $a_{x,y}$，一共有三种情况，分别列举一下：

初始值为 $1$。

此时不需要经过变换，直接输出 $0$。

经过若干次变换都不会变为 $1$。

这种情况显然输出 $-1$。但是该如何判断它呢？

考虑一下，在 $n \times m$ 的方阵中，若有两个数 $a_{x_1,y_1}$ 与 $a_{x_2,y_2}$ 满足 $\gcd(a_{x_1,y_1},a_{x_2,y_2}) = 1$，那么经过若干次的变换后一定能使所有的位置上的数变为 $1$。

在一次变换后的相关的 $5$ 个位置，都会变为 $1$ 或者是它们中的某一个数。也就是说以每个点为中心的 $5$ 个位置都会改变。因此上述的情况是成立的。

也就是把该方阵中的所有数做一遍 $\gcd$，若答案不为 $-1$，也就是无解的标志。

在有限次数内能变为 $1$。

首先考虑暴力，模拟每一次的变换过程，大概能拿到 $45\texttt{Pts}$ 的好成绩。

看回到情况 $2$，随手拿几个样例推一下，发现若 $\gcd(a_{x,y},a_{x’,y’}) = 1$，需要 $|x - x’| + |y - y’|$ 次后才能变换为 $1$。这不就是曼哈顿距离嘛，这样也就好写了。

最后放一个伪代码，同时也祝大家在 $2021$ 年中 $\texttt{rp++}$。


int main ()
{
    for (int i = 1;i <= n;++i)//n * m 的一遍 gcd
    {
        for (int j = 1;j <= m;++j)
        {
            if (i == 1 && j == 1) all = a[i][j];
            else all = work (all,a[i][j]);
        }
    }
    if (all != 1)//特判
    {
        printf ("-1\n");
        return 0;
    }
    if (a[x][y] == 1)//特判
    {
        printf ("0\n");
        return 0;
    }
    for (int i = 1;i <= n;++i)
    {
        for (int j = 1;j <= m;++j)
        {
            if (i == x && j == y) continue;//起点位置
            if (abs (x - i) + abs(y - j) >= ans) continue;//一个小优化
            if (work (a[i][j],a[x][y]) == 1) ans = min (ans,abs (x - i) + abs(y - j));
        }
    } 
    printf ("%lld\n",ans);
    return 0;
}
ll work (ll x,ll y)//辗转相除
{
    return (y == 0 ? x : work (y,x % y));
}