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

PyL0 · 2026-04-25 17:58:32 · 题解

思路

• 最终答案一定是 \gcd(a_{1,1}, a_{n,n}) 的某个约数，因为路径上的 \gcd 不会超过这个值。
• 设 g = \gcd(a_{1,1}, a_{n,n})，枚举 g 的所有约数 i，从大到小检查是否存在一条路径，使得路径上所有格子都被 i 整除。
• 若所有约数都不可行，输出 1。 ::::success[AC]

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
  cin.tie(0) -> sync_with_stdio(0);
  int n, v;
  cin >> n >> v;
  vector<vector<int> > a(n, vector<int>(n));
  vector<int> fac;
  vector<char> dp(n);
  for(int i = 0; i < n; i ++){
      for(int j = 0; j < n; j ++){
          cin >> a[i][j];
      }
  }
  int g = __gcd(a[0][0], a[n - 1][n - 1]);
  for(int i = 1; i * i <= g; i ++){
      if(g % i == 0){
          fac.push_back(i);
          if(i != g / i) fac.push_back(g / i);
      }
  }
  sort(fac.rbegin(), fac.rend());
  for(int i : fac){
      dp[0] = (a[0][0] % i == 0);
      for(int j = 1; j < n; j ++){
          dp[j] = dp[j - 1] && (a[0][j] % i == 0);
      }
      for(int j = 1; j < n; j ++){
          dp[0] = dp[0] && (a[j][0] % i == 0);
          for(int k = 1; k < n; k ++){
              if(a[j][k] % i == 0) dp[k] = dp[k] || dp[k-1];
              else dp[k] = 0;
          }
      }
      if(dp[n - 1]){
          cout << i;
          return 0;
      }
  }
  cout << '1';
  return 0;
  }

  ::::