制作网站需要多少费用,做甜品台的网站,商丘建设厅网站首页,小程序开发源码题目链接 给一个n*m的矩阵#xff0c; 删除里面的一行一列#xff0c; 使得剩下的数的最大公约数最大。 一个格子#xff08;x#xff0c;y#xff09;#xff0c; 先预处理出#xff08;1,1)到这个格子的内所有数的最大公约数#xff0c; 同理处理出(1, m), (n, m), (…题目链接 给一个n*m的矩阵 删除里面的一行一列 使得剩下的数的最大公约数最大。 一个格子xy 先预处理出1,1)到这个格子的内所有数的最大公约数 同理处理出(1, m), (n, m), (n, 1) 然后枚举格子中的每一个数 具体看代码。 #includebits/stdc.h
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
const int maxn 1080;
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 0?a:gcd(b, a%b);
}
int main()
{int n, m;while(cinnm) {for(int i 1; in; i) {for(int j 1; jm; j)scanf(%d, init[i][j]);}mem(a); mem(b); mem(c); mem(d);for(int i 1; in; i) {for(int j 1; jm; j) {a[i][j] gcd(a[i][j-1], a[i-1][j]);a[i][j] gcd(a[i][j], init[i][j]);}}for(int i 1; in; i) {for(int j m; j1; j--) {b[i][j] gcd(b[i][j1], b[i-1][j]);b[i][j] gcd(b[i][j], init[i][j]);}}for(int i n; i1; i--) {for(int j 1; jm; j) {c[i][j] gcd(c[i][j-1], c[i1][j]);c[i][j] gcd(c[i][j], init[i][j]);}}for(int i n; i1; i--) {for(int j m; j1; j--) {d[i][j] gcd(d[i][j1], d[i1][j]);d[i][j] gcd(d[i][j], init[i][j]);}}int ans 0;for(int i 1; in; i) {for(int j 1; jm; j) {int tmp1 gcd(a[i-1][j-1], b[i-1][j1]);int tmp2 gcd(c[i1][j-1], d[i1][j1]);ans max(ans, gcd(tmp1, tmp2));}}coutansendl;}return 0;
} 转载于:https://www.cnblogs.com/yohaha/p/5063196.html
