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

New_Void · 2026-04-25 13:48:30 · 题解

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

思路

注意到 V 初始是等于 a_{1,1} 的，且最后答案必然为 a_{1,1} 和 a_{n,n} 的最大公约数。注意到进行一次 gcd 操作定然不会使得结果变大，且每次操作定然为前驱所有节点 gcd 后的约数 ，所以我们其答案必然为 a_{1,1} 和 a_{n,n} 的最大公约数的约数，因数分解后，枚举每个因数做可达性 dp 即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
#define ls (u<<1)
#define rs (u<<1|1)
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
const int N=1010;
int a[N][N];
bool dp[N][N];
vector<int> v;
void solve(){
    int n=read(),V=read();
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++) a[i][j]=read();
    }
    V=__gcd(a[1][1],a[n][n]);
    for (int i=1;i<=V;i++){
        if (V%i==0) v.push_back(i);
    }
    sort(v.begin(),v.end(),greater<int>());
    for (int x:v){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++) dp[i][j]=0;
        }
        dp[1][1]=dp[0][0]=dp[1][0]=dp[0][1]=1;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (a[i][j]%x==0) dp[i][j]=dp[i-1][j]|dp[i][j-1];
            }
        }
        if (dp[n][n]){
            write(x);
            break;
        }
    }
}
signed main(){
    int T=1;
    while (T--) solve();
    return 0;
}
// ARIS0_0 16 祝好