题解：CF1955G GCD on a grid

pengziyippp · 2025-07-10 17:15:11 · 题解

题目大意

对于 n \times m 的网格中，每一个格子都有一个对应的 a[i][j]，求出从 a[1][1] 到 a[n][m] 路径中所有数的最大公约数所能达到的最大值。

思路简述

好水的绿题。 观察到数据范围 n,m 较小，且 a[i][j] \le 10^6。
考虑暴力乱搞。
由于所有路径必定经过 a[1][1]，所以最后输出的答案必定为 a[1][1] 的因数。
故而我们可以先找出 a[1][1] 的所有因数，从大到小到暴力枚举答案，每个检验一下是否存在合法方案，若存在，则输出。
如何检验呢。
考虑用 f[i][j] 表示第 i 行 j 列的位置是否可以到达，则转移方程可以表示为：

这里存约数时使用优先队列或者开个数组排序一下都可以，个人认为优先队列更方便一些，所以我是使用优先队列实现的。
这里要记得每次检验答案是否成立时要清空 f 数组和队列，而且 memset 容易超时。
结合代码看看挺好懂的，结束撒花撒花。

代码实现

CF提交记录
马蜂良好。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int a[N][N], f[N][N]; 
priority_queue<int> q;
int n, m; 
bool check (int x) { // 检验 
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = 0;
        }
    }
    f[1][1] = 1; // 初始化 
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            if (i == 1 && j == 1) continue;
            if (a[i][j] % x == 0) {  
                f[i][j] = f[i - 1][j] | f[i][j - 1]; // 从上方和左边转移 
            }
        }
    }
    return f[n][m]; // 返回 
}
void solve () {
    while (!q.empty()) q.pop(); // 清空 
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= sqrt(a[1][1]); i ++ ) {
        if (a[1][1] % i == 0) {
            q.push(i); q.push(a[1][1] / i);
        }
    } // 处理因数 
    while (!q.empty()) {
        int x = q.top(); q.pop();
        if (check(x)) { // 检验 
            cout << x << "\n";
            return;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) solve();
}