BUAA 更大公约数

题目链接

给一个n*m的矩阵， 删除里面的一行一列， 使得剩下的数的最大公约数最大。

一个格子（x，y）， 先预处理出（1,1)到这个格子的内所有数的最大公约数， 同理处理出(1, m), (n, m), (n, 1)， 然后枚举格子中的每一个数， 具体看代码。

#include<bits/stdc++.h>

using namespace std;

#define mem(a) memset(a, 0, sizeof(a))

const int maxn = ;

int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];

int init[maxn][maxn];

int gcd(int a, int b) {

    return b == ?a:gcd(b, a%b);

}

int main()

{

    int n, m;

    while(cin>>n>>m) {

        for(int i = ; i<=n; i++) {

            for(int j = ; j<=m; j++)

                scanf("%d", &init[i][j]);

        }

        mem(a); mem(b); mem(c); mem(d);

        for(int i = ; i<=n; i++) {

            for(int j = ; j<=m; j++) {

                a[i][j] = gcd(a[i][j-], a[i-][j]);

                a[i][j] = gcd(a[i][j], init[i][j]);

            }

        }

        for(int i = ; i<=n; i++) {

            for(int j = m; j>=; j--) {

                b[i][j] = gcd(b[i][j+], b[i-][j]);

                b[i][j] = gcd(b[i][j], init[i][j]);

            }

        }

        for(int i = n; i>=; i--) {

            for(int j = ; j<=m; j++) {

                c[i][j] = gcd(c[i][j-], c[i+][j]);

                c[i][j] = gcd(c[i][j], init[i][j]);

            }

        }

        for(int i = n; i>=; i--) {

            for(int j = m; j>=; j--) {

                d[i][j] = gcd(d[i][j+], d[i+][j]);

                d[i][j] = gcd(d[i][j], init[i][j]);

            }

        }

        int ans = ;

        for(int i = ; i<=n; i++) {

            for(int j = ; j<=m; j++) {

                int tmp1 = gcd(a[i-][j-], b[i-][j+]);

                int tmp2 = gcd(c[i+][j-], d[i+][j+]);

                ans = max(ans, gcd(tmp1, tmp2));

            }

        }

        cout<<ans<<endl;

    }

    return ;

}