fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = 3007;
  14.  
  15. int n , m , a[maxN] , b[maxN] , c[maxN];
  16. vector<pair<ii , ii>> tmp;
  17. int t[maxN];
  18. vector<int> g[maxN];
  19.  
  20. void prepare(){
  21.     for (int i = 1 ; i < maxN ; i++){
  22.         for (int x = i ; x < maxN  ; x += x&-x) g[i].push_back(x);
  23.     }
  24. }
  25.  
  26. void update(int x , int y){
  27.     for (; x < maxN ; x += x&-x) t[x] = max(t[x] , y);
  28. }
  29.  
  30. int get(int x){
  31.     int ans = 0;
  32.     for (; x >= 1 ; x -= x&-x) ans = max(ans , t[x]);
  33.     return ans;
  34. }
  35.  
  36. void solve(){
  37.     cin >> n >> m;
  38.     for (int i = 1 ; i <= n ; i++) cin >> a[i];
  39.     for (int i = 1 ; i <= m ; i++) cin >> b[i];
  40.     sort(a + 1 , a + n + 1);
  41.     sort(b + 1 , b + m + 1);
  42.     for (int i = 1 ; i <= n ; i++){
  43.         for (int j = 1 ; j <= m ; j++){
  44.             int x = __gcd(a[i] , b[j]);
  45.             ii it = {a[i] / x , b[j] / x};
  46.             tmp.push_back({it , {i , j}});
  47.         }
  48.     }
  49.     sort(all(tmp));
  50.     int l = 0 , r = -1 , ans = 0;
  51.     while (l < sz(tmp)){
  52.         while (r + 1 < sz(tmp) && tmp[l].fi == tmp[r + 1].fi) r++;
  53.         int L = l , R = l - 1;
  54.         while (L <= r){
  55.             while (R + 1 <= r && tmp[L].se.fi == tmp[R + 1].se.fi) R++;
  56.             for (int i = R ; i >= L ; i--){
  57.                 int x = tmp[i].se.se;
  58.                 int y = get(x - 1) + 1;
  59.                 update(x , y);
  60.                 ans = max(ans , y);
  61.             }
  62.             L = R + 1;
  63.         }
  64.         for (int i = l ; i <= r ; i++){
  65.             int x = tmp[i].se.se;
  66.             for (int y : g[x]) t[y] = 0;
  67.         }
  68.         l = r + 1;
  69.     }
  70.     cout << n + m - ans << "\n";
  71.     tmp.clear();
  72. }
  73.  
  74. #define name "G"
  75.  
  76. int main(){
  77.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  78.     if (fopen(name".INP" , "r")){
  79.         freopen(name".INP" , "r" , stdin);
  80.         freopen(name".OUT" , "w" , stdout);
  81.     }
  82.     prepare();
  83.     int t = 1; cin >> t;
  84.     while (t--) solve();
  85.     return 0;
  86. }
  87.  
  88.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/M4nwGv
language:
C++ (gcc 8.3)
created:
7 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!