我们暴力枚举可能的答案 \(k\)，然后跑一边 dp。
设 \(f_{i,j}\) 表示在格子 \((i,j)\) 是否可以满足有一条路径可以到达该格子且该格子是否为 \(k\) 的倍数，递推式即为 \(f_{i,j}=(k\mid a_{i,j} \operatorname{and} (f_{i-1,j} \operatorname{or} f_{i,j-1}))\) 最后的答案即是 \(f_{n,m}\)。
时间复杂度 \(O(nm\log{V})\)，其中 \(V\) 是值域。
点击查看代码
bool check(int k) {
m0(f);
f[1][1]=1;
For(i,1,n) For(j,1,m) {
if(a[i][j]%k==0) {
f[i][j]|=f[i-1][j]|f[i][j-1];
}
}
return f[1][1]&f[n][m];
}
void work() {
in2(n,m);
For(i,1,n) inn(a[i],m);
int g=__gcd(a[1][1],a[n][m]);
int ans=0;
for(int i=1;i*i<=g;i++){
if(g%i==0) {
if(check(i))
ans=max(ans,i);
if(check(g/i))
ans=max(ans,g/i);
}
}
cout<<ans<<'\n';
}