Cards (AOJ 1163) by mzsrkn10
Contest: 3575    RunID: 2376254    Status: Accepted    Date: Sat Jun 17 16:39:20 JST 2017


#include<bits/stdc++.h>
using namespace std;

int b[501] = {0}, r[501] = {0};

bool augment(const vector<int> g[], int src,
    vector<int>& matchTo, vector<bool>& visited) {
  if (src < 0) return true;
  for(auto dst : g[src]) if (!visited[dst]) {
    visited[dst] = true;
    if (augment(g, matchTo[dst], matchTo, visited)) {
      matchTo[src] = dst;
      matchTo[dst] = src;
      return true;
    }
  }
  return false;
}

int bipartiteMatching(const vector<int> g[], int m, int n) {
  vector<int> matchTo(m + n, -1);
  int match = 0;
  for(int u=0;u<m;++u) {
    vector<bool> visited(m + n);
    if (augment(g, u, matchTo, visited)) ++match;
  }

  return match;
}

int gcd(int a, int b){
    return (b != 0 ? gcd(b, a % b) : a);
}

int main(){
    int m, n;
    while(cin >> m >> n, m != 0 || n != 0){
        for(int i=0;i<m;++i)cin >> b[i];
        for(int i=0;i<n;++i)cin >> r[i];
        vector<int> g[m+n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(gcd(b[i], r[j]) != 1){
                    g[i].push_back(m + j);
                    g[m + j].push_back(i);
                }
            }
        }
        int ans = bipartiteMatching(g, m, n);
        cout << ans << endl;
    }

    return 0;
}