fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #include<ext/pb_ds/assoc_container.hpp>
  3. // #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. // using namespace __gnu_pbds;
  6. #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
  7. #define ll long long
  8. #define int ll
  9. #define endll "\n"
  10. #define read(x) int x; cin>>x;
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define mp make_pair
  14. #define ff first
  15. #define ss second
  16. #define all(x) (x).begin(), (x).end()
  17. #define py cout << "YES\n"
  18. #define pn cout << "NO\n"
  19. #define fr(i, a, b) for (int i = a; i < b; i++)
  20. #define fer(i, a, b) for (int i = a; i <= b; i++)
  21. #define frr(i, a, b) for (int i = a; i >= b; i--)
  22. #define rev(v) v.rbegin(), v.rend()
  23. #define sz(v) (int)v.size()
  24. #define vecin(v, n) vll v(n); for (int &x : v) cin >> x
  25. #define vecin1(v, n) vll v(n + 1); v[0] = 0; fer (i, 1, n) cin >> v[i]
  26. #define vecp(v) { for (auto x : v) cout << x << ' '; cout << endl; }
  27. using vll = vector<int>;
  28. using vbl = vector<bool>;
  29. using pll = pair<int, int>;
  30. using vpll = vector<pll>;
  31. using vvll = vector<vll>;
  32. using vgr = vector<vpll>;
  33. using stll = set<int>;
  34. using mpll = map<int, int>;
  35. using mpvll = map<int, vll>;
  36. // typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
  37. // a.find_by_order(num) iterator dega uss no ka , a.order_of_key(num)(number of element smaller that that num)
  38.  
  39. #define inf numeric_limits<long long>::max()
  40. const long long MOD = 1000000007;
  41.  
  42.  
  43.  
  44.  
  45. long long power(long long a, long long b)
  46. {
  47.     long long res = 1;
  48.     while (b) {
  49.         if (b & 1) res = res * a;
  50.         a = a * a;
  51.         b >>= 1;
  52.     }
  53.     return res;
  54. }
  55.  
  56.  
  57.  
  58. bool sortByCond(const pair<ll, ll> &a, const pair<ll, ll> &b)
  59. {
  60.     /*
  61.         if (a.ff == b.ff)
  62.             return a.ss < b.ss;
  63.         else
  64.             return a.ff < b.ff;
  65.     */
  66.     return a.ss < b.ss;
  67. }
  68.  
  69.  
  70. vector<int> divisors(int num)
  71. {
  72.     vector<int>d;
  73.     fer(i,1,sqrt(num))
  74.     {
  75.         if(num % i == 0)d.pb(i);
  76.         if(i != num/i)d.pb(num/i);
  77.     }
  78.  
  79.     return d;
  80. }
  81.  
  82.  
  83. bool bfs(int num,vvll &v)
  84. {
  85.     int n = v.size();
  86.     int m = v[0].size();
  87.     queue<pair<int,int>>q;
  88.     vector<vbl>vis(n,vbl(m,0));
  89.     q.push({0,0});
  90.     int dx[] = {1,0};
  91.     int dy[] = {0,1};
  92.     vis[0][0] = 1;
  93.     while (!q.empty())
  94.     {
  95.         int x = q.front().ff;
  96.         int y = q.front().ss;
  97.         q.pop();
  98.         fr(i,0,2)
  99.         {
  100.             int nx = x + dx[i];
  101.             int ny = y + dy[i];
  102.             if(nx < n && ny < m && !vis[nx][ny] && v[nx][ny]%num == 0)
  103.             {
  104.                 if(nx == n-1 && ny == m-1)return true;
  105.                 vis[nx][ny] = 1;
  106.                 q.push({nx,ny});
  107.             }
  108.  
  109.         }
  110.     }
  111.     return false;
  112. }
  113.  
  114.  
  115. void solve()
  116. {
  117.     int n,m;
  118.     cin>>n>>m;
  119.     vvll v(n, vll(m, 0));
  120.     fr(i,0,n)
  121.     {
  122.         fr(j,0,m)
  123.         {
  124.             cin>>v[i][j];
  125.         }
  126.     }
  127.     vll div = divisors(__gcd(v[0][0],v[n-1][m-1]));
  128.     int val = sqrt(__gcd(v[0][0],v[n-1][m-1]));
  129.     int ans = 1;
  130.     if (sqrt(val)==(int)sqrt(val))
  131.             if(bfs(sqrt(val),v))ans = max(ans,val);
  132.     sort(all(div));
  133.     frr(i,div.size()-1,0)
  134.     {
  135.         if(bfs(div[i],v))
  136.         {
  137.             ans = max(div[i],ans);
  138.             break;
  139.         }
  140.     }
  141.     cout<<ans<<endll;
  142. }
  143.  
  144.  
  145.  
  146.  
  147. int32_t main()
  148. {
  149.     fast_io;
  150.     int t = 1;
  151.     cin >> t;
  152.     fer (i, 1, t)
  153.     {
  154.         // cout << "Test Case " << i << endl;
  155.         solve();
  156.     }
  157.     return 0;
  158. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
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
stdout
copy 
10
3
1
https://ideone.com/zZgeB8
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!