fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define alsammany ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define debugg(x, y) cout<<#x<<" = "<<x<<", "<<#y<<" = "<<y<< endl
  5. #define debug(x) cout<<#x<<" = "<<x<<endl
  6. #define raint(v) v.rbegin(),v.rend()
  7. #define aint(v) v.begin(),v.end()
  8. #define mem(dp, val) memset(dp, val, sizeof(dp))
  9. #define F first
  10. #define S second
  11. #define endl "\n"
  12. #define int long long
  13. #define rc(r, c, v) vector<vector<node>>(r, vector<node>(c, v))
  14. template <typename T> void display(const T& container) { cout << "{ "; for (const auto& element : container) { cout << element << " "; } cout << "}" << endl; } template <typename K, typename V> void display(const map<K, V>& container) { for (const auto& pair : container) { cout << "\n[" << pair.first << "]: "; display(pair.second); } }
  15. const int N = 1e5+5;
  16. const int M = 1e9+7;
  17. const int inf = 0x3f3f3f3f3f3f3f3f;
  18.  
  19. //  [سورة البلد: 4]  ﴾ لَقَدْ خَلَقْنَا الْإِنسَانَ فِي كَبَدٍ ﴿ <------ 
  20.  
  21. int spf[N];
  22. void sv(){
  23.     for(int i=2; i<N; i++){
  24.         if(!spf[i]){
  25.             for(int j=i; j<N; j+=i){
  26.                 if(!spf[j]){
  27.                     spf[j] = i;
  28.                 }
  29.             }
  30.         }
  31.     }
  32. }
  33.  
  34. map<int, int> prime_fact(int x){
  35.     map<int,int> mp;
  36.     while(x>1){
  37.         mp[spf[x]]++;
  38.         x /= spf[x];
  39.     }
  40.     return mp;
  41. }
  42.  
  43. vector<int> v;
  44. void gen(int div, map<int,int>::iterator it, map<int,int> &mp){ 
  45.     if(it == mp.end()){
  46.         v.push_back(div);
  47.         return;
  48.     }
  49.     for(int i=0, d=1; i<=it->second; i++, d*=it->first){
  50.         gen(div*d, ++it, mp);
  51.         it--;
  52.     }
  53. }
  54.  
  55. vector<int> divs[N];
  56. bool vis[N];
  57.  
  58.  
  59. struct node{
  60.     int val, id;
  61. };
  62.  
  63. int n,m;
  64. vector<vector<node>> mat;
  65.  
  66. int dx[4] = {1,0,0,-1}; // D L R U
  67. int dy[4] = {0,-1,1,0};
  68.  
  69. bool in(int r, int c){
  70.     if(r < 0 || c < 0 || r > n-1 || c > m-1) return 0;
  71.     return 1;
  72. }
  73.  
  74. struct DSU {
  75.     map<int, int> parent, size;
  76.  
  77.     int mx = 0;
  78.  
  79.     void init(int val) {
  80.         parent[val] = val;
  81.         size[val] = 1;
  82.         mx = 1;
  83.     }
  84.     void add(int val) {
  85.         parent[val] = val;
  86.         size[val] = 1;
  87.     }
  88.  
  89.     int find_root(int u) {
  90.         if (parent[u] == u) return u;
  91.         return parent[u] = find_root(parent[u]);
  92.     }
  93.  
  94.     bool merge(int u, int v) {
  95.         int root_u = find_root(u);
  96.         int root_v = find_root(v);
  97.  
  98.         if (root_u == root_v) return 0;
  99.  
  100.         if (size[root_u] > size[root_v]) swap(root_u, root_v);
  101.         parent[root_u] = root_v;
  102.         size[root_v] += size[root_u];
  103.         mx = max(mx, size[root_v]);
  104.         return 1;
  105.     }
  106.  
  107.     int maxi(){
  108.         return mx;
  109.     }
  110. };
  111.  
  112. void Solve(){   
  113.     cin>>n>>m;
  114.     int rid = 1;
  115.     mat = vector<vector<node>>(n, vector<node>(m, {0,0}));
  116.     vector<pair<int,int>> loc(N);
  117.     for(int i=0; i<n; i++){
  118.         for(int j=0; j<m; j++){
  119.             cin>>mat[i][j].val;
  120.             mat[i][j].id = rid;
  121.             loc[rid] = {i,j};
  122.             rid++;
  123.  
  124.  
  125.                 auto fp = prime_fact(mat[i][j].val);
  126.                 v.clear();
  127.                 gen(1, fp.begin(), fp);
  128.                 for(auto d:v){
  129.                     divs[d].push_back(mat[i][j].id);
  130.                 }
  131.  
  132.         }
  133.     }
  134.  
  135.  
  136.     vector<int> ans(n*m + 1);
  137.     int prv = 0;
  138.     // map<int, DSU> mp;
  139.  
  140.     for(int d=N-1; d>0; d--){
  141.         DSU st;
  142.         for(auto id:divs[d]){
  143.             if(!st.mx) st.init(id);
  144.             else st.add(id);
  145.             auto [i,j] = loc[id];
  146.             for(int dir=0; dir<4; dir++){
  147.                 int r = i + dx[dir];
  148.                 int c = j + dy[dir];
  149.                 if(in(r,c) && st.parent.count(mat[r][c].id)){ // alreay in dsu
  150.                     // join
  151.                     st.merge(id, mat[r][c].id);
  152.                 }
  153.             }
  154.         }
  155.  
  156.         int mx = st.maxi();
  157.         if(mx > prv){
  158.             for(int i=prv+1; i<=mx && i<n*m+1; i++){
  159.                 ans[i] = d;
  160.             }
  161.             prv = mx;
  162.         }
  163.     }
  164.  
  165.  
  166.     for(int i=1; i<=n*m; i++){
  167.         cout<<ans[i]<<' ';
  168.     }
  169.  
  170. }
  171.  
  172. int32_t main(){
  173.     alsammany
  174.     sv();
  175.     // freopen("input.in", "r", stdin); 
  176.     // freopen("output.out", "w", stdout); 
  177.     int t = 1;
  178.  
  179.     // cin >> t;
  180.  
  181.     while(t--){
  182.         Solve();
  183.         // cout << endl;
  184.     }
  185.     return 0;
  186. }
Success #stdin #stdout 0.01s 7812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J9oKBG
language:
C++14 (gcc 8.3)
created:
23 hours 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!