题解：P16343 [科大国创杯初中组 2026] 行走
nyt_nyt2012
·
·
题解
注意到 a_{i,j}\le10^4，显然我们的时间复杂度与 a_{i,j} 有关。注意到答案在不断取最大公因数的时候一定取了 a_{1,1} 的因数。\
\
我们可以找一下小于 10^4 的数的因数个数，发现其最多有 64 个因数。
#include<bits/stdc++.h>
using namespace std;
int main(){
int ans=0;
for(int k=1;k<=10000;k++){
int num=0;
for(int i=1;i*i<=k;i++){
if(k%i==0)num+=2;
if(i*i==k)num--;
}
ans=max(ans,num);
}
cout<<ans<<endl;
return 0;
}//输出：64
我们就可以枚举每一个 a_{1,1} 的因数，用动态规划求出每一个点的 v 可否为该因数的倍数。转移方程自此浮出水面：
\
显然上式对空间的开销是极大的，所以我们可以把 $k$ 映射到 $1\sim64$ 的小一点的数中，已经足以通过此题。我们还可以干脆舍弃 $k$ 这一维度，用二维 $dp$ 数组一次记录一个 $k$ 的信息。我们还可以使用 `bitset` 优化常数。下面就是代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
short n,a[1002][1002],y[100],v;
bitset<1001>dp[1001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>v;
for(short i=1;i<=n;i++){
for(short j=1;j<=n;j++){
cin>>a[i][j];
}
}
short tot=0;
for(short i=1;i<=1000;i++){
if(a[1][1]%i==0){
y[++tot]=i;
}
}
dp[0][1]=dp[1][0]=1;
short ans=1;
for(short k=1;k<=tot;k++){
for(short i=1;i<=n;i++){
for(short j=1;j<=n;j++){
dp[i][j]=(dp[i][j-1]||dp[i-1][j])&&(a[i][j]%y[k]==0);
}
}
if(dp[n][n])ans=k;
}
cout<<y[ans];
return 0;
}
```
空间还能有本质优化吗？