cf diff
1 removal
68 lines
7 additions
74 lines
#include <iostream>
#include <iostream>
#include <vector>
#include <vector>
#define int long long
#define int long long
int gcd(int a, int b) {
int gcd(int a, int b) {
if (b == 0) return a;
if (b == 0) return a;
return gcd(b, a % b);
return gcd(b, a % b);
}
}
std::vector<std::vector<bool>> isposs;
bool isPoss(int value, std::vector<std::vector<int>> &grid) {
bool isPoss(int value, std::vector<std::vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
int n = grid.size(), m = grid[0].size();
std::vector<std::vector<bool>> isposs(n, std::vector<bool>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
isposs[i][j] = 0;
}
}
isposs[0][0] = 1;
isposs[0][0] = 1;
for (int i = 1; i < m; i++) {
for (int i = 1; i < m; i++) {
if (grid[0][i] % value == 0 && isposs[0][i - 1]) isposs[0][i] = 1;
if (grid[0][i] % value == 0 && isposs[0][i - 1]) isposs[0][i] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int i = 1; i < n; i++) {
if (grid[i][0] % value == 0 && isposs[i - 1][0]) isposs[i][0] = 1;
if (grid[i][0] % value == 0 && isposs[i - 1][0]) isposs[i][0] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
for (int j = 1; j < m; j++) {
if (grid[i][j] % value == 0 &&
if (grid[i][j] % value == 0 &&
(isposs[i][j - 1] || isposs[i - 1][j]))
(isposs[i][j - 1] || isposs[i - 1][j]))
isposs[i][j] = 1;
isposs[i][j] = 1;
}
}
}
}
return isposs[n - 1][m - 1];
return isposs[n - 1][m - 1];
}
}
void solve() {
void solve() {
int n, m;
int n, m;
std::cin >> n >> m;
std::cin >> n >> m;
isposs.resize(n, std::vector<bool>(m));
std::vector<std::vector<int>> grid(n, std::vector<int>(m));
std::vector<std::vector<int>> grid(n, std::vector<int>(m));
for (int i = 0; i < n; i++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int j = 0; j < m; j++) {
std::cin >> grid[i][j];
std::cin >> grid[i][j];
}
}
}
}
int res = gcd(grid[0][0], grid[n - 1][m - 1]);
int res = gcd(grid[0][0], grid[n - 1][m - 1]);
int ans = 1;
int ans = 1;
for (int i = 1; i * i <= res; i++) {
for (int i = 1; i * i <= res; i++) {
if (res % i) continue;
if (res % i) continue;
int div = res / i;
int div = res / i;
if (isPoss(div, grid)) {
if (isPoss(div, grid)) {
std::cout << div << "\n";
std::cout << div << "\n";
return;
return;
}
}
if (i != 1 && isPoss(i, grid)) ans = i;
if (i != 1 && isPoss(i, grid)) ans = i;
}
}
std::cout << ans << "\n";
std::cout << ans << "\n";
}
}
signed main() {
signed main() {
std::ios::sync_with_stdio(false);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin.tie(0);
std::cout.tie(0);
std::cout.tie(0);
int t;
int t;
std::cin >> t;
std::cin >> t;
while (t--) {
while (t--) {
solve();
solve();
}
}
return 0;
return 0;
}
}