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

ARIS0_0 · 2026-04-25 13:10:59 · 题解

小清新题。

考虑到点 (1,1) 一定位于路径上，所以答案一定是 a_{1,1} 的因数。

考虑从大到小枚举因数，对于每个因数 d，我们寻找一条路径，使路径上的所有点都是 d 的倍数。

不难想到使用 BFS 解决。

最大时间复杂度 O(a_{1,1}n^2)，但实际快很多。

实在不行可以使用 O(\sqrt{a_{1,1}}) 的方式枚举因数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,v,a[1010][1010],vis[1010][1010];
queue<pair<int,int> >q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    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(vis,0,sizeof vis);
            while(!q.empty()){
                q.pop();
            }
            q.push(make_pair(1,1)),vis[1][1]=1;
            while(!q.empty()){
                int x=q.front().first,y=q.front().second;
                q.pop();
                if(x==n&&y==n){
                    break;
                }
                if(a[x+1][y]%i==0&&x+1<=n&&y<=n&&!vis[x+1][y]){
                    q.push(make_pair(x+1,y)),vis[x+1][y]=1;
                }
                if(a[x][y+1]%i==0&&x<=n&&y+1<=n&&!vis[x][y+1]){
                    q.push(make_pair(x,y+1)),vis[x][y+1]=1;
                }
            }
            if(vis[n][n]){
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}
// 以点点繁星，汇日日天明
// 14