题目描述

不久前，Egor 学习了求两个数的最大公约数的欧几里得算法。两个数 $a$ 和 $b$ 的最大公约数是除以 $a$ 和 $b$ 而不留余数的最大数。有了这些知识，埃戈就能解决他曾经无法解决的问题了。

瓦西里有一个 $n$ 行和 $m$ 列的网格，整数 ${a_i}_j$ 位于 $i$ 行和 $j$ 列的交点上。Egor 想从左上角（第一行和第一列的交点）移动到右下角（最后一行和最后一列的交点），并找出路径上所有数字的最大公约数。他只能向下和向右移动。Egor 写下了几条路径，并得到了不同的 GCD 值。他开始对寻找最大可能的 GCD 感兴趣。

不幸的是，Egor 已经厌倦了计算 GCD，因此他请求您帮助他找出从网格左上角到右下角的路径上整数的最大 GCD。

输入

第一行包含一个整数 $t$ ( $1 \le t \le {10}^{4}$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $1 \le n, m \le 100$ )–网格的行数和列数。

然后是 $n$ 行，其中第 $i$ 行包含 $m$ 个整数（ $(1 \le a_{i,j} \le {10}^{6}$ ）–写入网格第 $i$ 行和第 $j$ 列的整数。

保证在所有测试案例中， $n \cdot m$ 的总和不超过 $2 \cdot {10}^{5}$ 。

输出

对于每个测试用例，另起一行输出从左上角单元格到右下角单元格的最大可能 GCD。

样例

input：

3
2 3
30 20 30
15 25 40
3 3
12 4 9
3 12 2
8 3 12
2 4
2 4 6 8
1 3 6 9

output:

10
3
1

解法

因为一定会经过a[1][1]与a[n][m]，所以路径上所有数字与a[1][1]与a[n][m]必有相同的约数。
所以枚举a[1][1]与a[n][m]的约束，利用dp算出是否存在这样的路径即可，然后记录满足条件的最大约数即可

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int g[N][N];
int dp[N][N];

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> g[i][j];

    int u = gcd(g[1][1], g[n][m]);
    //for(auto i : all) cout << i << ' '; cout << endl;
    int ans = 0;
    for(int k = 1; k * k <= u; k++){//枚举约束
        if(u % k) continue;
        int divnum[2] = {k, u / k};
        for(int p = 0; p < 2; p++){
            int num = divnum[p];
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    dp[i][j] = 0;
                    if(i == 1 && j == 1) dp[i][j] = 1;
                    if(g[i][j] % num == 0){
                        if(i > 1 && dp[i - 1][j] == 1) dp[i][j] = 1;
                        if(j > 1 && dp[i][j - 1] == 1) dp[i][j] = 1;
                    }
                }
            }
            if(dp[n][m] == 1){
                ans = max(ans, num);
            }
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--){
        solve();
    }

    return 0;
}