题解：P16343 [科大国创杯初中组 2026] 行走

大宋宝宝 · 2026-04-23 20:16:22 · 题解

由于小可可走路的时候在不停的取最大公因数，所以最后答案一定是 a_{1,1} 的一个因数。

注意到 a_{1,1} 在 10000 以内，它的因数个数最多有 64 个，考虑枚举答案。

枚举答案后如何验证？

我们知道，如果小可可走过的路径上所有数的最大公因数为 x ，则路径上所有数都是 x 的倍数。

所以可以枚举答案 x ，然后判断是否存在一条路线满足此路线上所有数都是 x 的倍数。

具体过程用动态规划实现，详见代码。

#include<bits/stdc++.h>
using namespace std;
int n,v,a[1010][1010];
bool dp[1010][1010];
int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=a[1][1];i>=1;i--)
    {
        if(a[1][1]%i==0)
        {
            memset(dp,0,sizeof(dp));
            dp[1][1]=1;
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    if((dp[j][k]||dp[j-1][k]||dp[j][k-1])&&a[j][k]%i==0)
                    {
                        dp[j][k]=1;
                    }
                }
            }
            if(dp[n][n])
            {
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}