HackerRank Computer Game Problem Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define LIM 32100
#define NUM 123456
typedef struct _node{
  int x;
  int id;
  struct _node *next;
} node;
typedef struct _list_node{
  int x;
  struct _list_node *next;
} list_node;
typedef struct _list{
  int size;
  list_node *head;
} list;
node **hash;
int *p,hash_size=0,*A,*B,*ALength,**AD,*BLength,**BD,*MA,*MB,*VA,*VB;
int match(int u,int vi);
void getp(long long N,int *prim);
int findid(int x,int iflag);
void freehash();
void insert(list *l,int x);
void freelist(list *l);

int main(){
  p=(int*)malloc(LIM*sizeof(int));
  hash=(node**)malloc(NUM*sizeof(node*));
  memset(hash,0,NUM*sizeof(node*));
  getp(LIM,p);
  int i,j,ans=0,n,t;
  scanf("%d",&n);
  A=(int*)malloc(n*sizeof(int));
  B=(int*)malloc(n*sizeof(int));
  int *Alist=(int*)malloc(13*sizeof(int));
  ALength=(int*)malloc(n*sizeof(int));
  AD=(int**)malloc(n*sizeof(int*));
  list_node *temp;
  for(i=0;i<n;i++)
    scanf("%d",A+i);
  for(i=0;i<n;i++)
    scanf("%d",B+i);
  for(i=0;i<n;i++){
    Alist[0]=0;
    for(j=0;p[j]*p[j]<=A[i];j++)
      if(A[i]%p[j]==0){
        Alist[++Alist[0]]=findid(p[j],1);
        while(A[i]%p[j]==0)
          A[i]/=p[j];
      }
    if(A[i]!=1)
      Alist[++Alist[0]]=findid(A[i],1);
    ALength[i]=Alist[0];
    AD[i]=(int*)malloc(Alist[0]*sizeof(int));
    for(j=0;j<Alist[0];j++)
      AD[i][j]=Alist[Alist[0]-j];
  }
  free(A);
  free(Alist);
  list *Blist=(list*)malloc(hash_size*sizeof(list));
  BLength=(int*)malloc(hash_size*sizeof(int));
  BD=(int**)malloc(hash_size*sizeof(int*));
  memset(Blist,0,hash_size*sizeof(list));
  for(i=0;i<n;i++){
    for(j=0;p[j]*p[j]<=B[i];j++)
      if(B[i]%p[j]==0){
        t=findid(p[j],0);
        if(t!=-1)
          insert(Blist+t,i);
        while(B[i]%p[j]==0)
          B[i]/=p[j];
      }
    if(B[i]!=1){
      t=findid(B[i],0);
      if(t!=-1)
        insert(Blist+t,i);
    }
  }
  for(i=0;i<hash_size;i++){
    BD[i]=(int*)malloc(Blist[i].size*sizeof(int));
    BLength[i]=Blist[i].size;
    j=Blist[i].size-1;
    temp=Blist[i].head;
    while(temp){
      BD[i][j]=temp->x;
      temp=temp->next;
      j--;
    }
    freelist(Blist+i);
  }
  free(B);
  free(Blist);
  free(p);
  freehash();
  MA=(int*)malloc(n*sizeof(int));
  MB=(int*)malloc(n*sizeof(int));
  VA=(int*)malloc(n*sizeof(int));
  VB=(int*)malloc(hash_size*sizeof(int));
  memset(MA,-1,n*sizeof(int));
  memset(MB,-1,n*sizeof(int));
  memset(VA,-1,n*sizeof(int));
  memset(VB,-1,hash_size*sizeof(int));
  for(i=0;i<n;i++)
    if(match(i,i))
      ans++;
  printf("%d",ans);
  return 0;
}
int match(int u,int vi){
  int i,j,v;
  if(VA[u]==vi)
    return 0;
  VA[u]=vi;
  int *FA=AD[u];
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MB[v]==-1){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    VB[FA[i]]=vi;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MA[u]!=v && match(MB[v],vi)){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  return 0;
}
void getp(long long N,int *prim){
  long long i,j,index=2,flag;
  prim[0]=2;
  prim[1]=3;
  for(i=5;i<=N;i=i+2)
    {
      for(j=1,flag=1;prim[j]<=sqrt(i);j++)
        {
          if(i%prim[j]==0){
            flag=0;
            break;}
        }
      if(flag==1)
        {prim[index]=i;
          index++;}
    }
  prim[index]=0;
  return;
}
int findid(int x,int iflag){
  int b=x%NUM;
  node *t=hash[b];
  while(t){
    if(t->x==x)
      return t->id;
    t=t->next;
  }
  if(iflag){
    t=(node*)malloc(sizeof(node));
    t->x=x;
    t->id=hash_size++;
    t->next=hash[b];
    hash[b]=t;
    return t->id;
  }
  return -1;
}
void freehash(){
  int i;
  node *t,*p;
  for(i=0;i<NUM;i++){
    t=hash[i];
    while(t){
      p=t->next;
      free(t);
      t=p;
    }
  }
  free(hash);
  return;
}
void insert(list *l,int x){
  list_node *t=(list_node*)malloc(sizeof(list_node));
  t->x=x;
  t->next=l->head;
  l->head=t;
  l->size++;
  return;
}
void freelist(list *l){
  list_node *t,*p;
  t=l->head;
  while(t){
    p=t->next;
    free(t);
    t=p;
  }
  return;
}

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>

using namespace std;

vector<bool> calcSieve(int maxValue) {
    vector<bool> isPrime = vector<bool>(maxValue, true);
    isPrime[0] = isPrime[1] = false;
    int L = sqrt(maxValue);

    for (int i = 2; i <= L; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < maxValue; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

vector<int> compressSieve(vector<bool> isPrime) {
    vector<int> primes;
    int maxValue = isPrime.size();

    for (int i = 2; i < maxValue; i++) {
        if (isPrime[i])
            primes.push_back(i);
    }

    return primes;
}

bool match(int u,
           int ** primeIdsA,
           int * primeIdsLength,
           int ** bMatchArr,
           int * bMatchLength,
           int * visitedL,
           int * visitedR,
           int * matchL,
           int * matchR,
           int visitedI) {
        if (visitedL[u] == visitedI)
            return false;
        visitedL[u] = visitedI;
        int * factors = primeIdsA[u];

        for (int i = 0; i < primeIdsLength[u]; i++) {
            if (visitedR[factors[i]] == visitedI)
                continue;
            for (int j = 0; j < bMatchLength[factors[i]]; j++) {
                int v = bMatchArr[factors[i]][j];
                if (matchR[v] < 0) {
                    matchL[u] = v;
                    matchR[v] = u;
                    return true;
                }
            }
        }

        for (int i = 0; i < primeIdsLength[u]; i++) {
            if (visitedR[factors[i]] == visitedI)
                continue;
            visitedR[factors[i]] = visitedI;
            for (int j = 0; j < bMatchLength[factors[i]]; j++) {
                int v = bMatchArr[factors[i]][j];
                if (matchL[u] != v && match(matchR[v], primeIdsA, primeIdsLength, bMatchArr, bMatchLength, visitedL, visitedR, matchL, matchR, visitedI)) {
                    matchL[u] = v;
                    matchR[v] = u;
                    return true;
                }
            }
        }

        return false;
           }
           int getPrimeId(int prime, std::map<int, int> & primeIds) {
               if (primeIds.find(prime) == primeIds.end())
                       primeIds[prime] = primeIds.size();
                return primeIds[prime];
           }

           int getMaximumRemovals(std::vector<int> a, std::vector<int> b) {
               static int MAX = 1000000000;
               std::vector<bool> isPrime = calcSieve(std::sqrt(MAX));
               std::vector<int> primes = compressSieve(isPrime);

               std::map<int, int> primeIds;
               int * primeFactors = new int[primes.size()];
               int ** primeIdsA = new int * [a.size()];
               int * primeIdsALength = new int[a.size()];

               for (unsigned int i = 0; i < a.size(); i++) {
                   int x = a[i];
                   int p = 0;
                   for (unsigned int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) {
                       if (x % primes[j] == 0)
                           primeFactors[p++] = primes[j];
                    while (x % primes[j] == 0)
                        x /= primes[j];
                   }
                   if (x > 1)
                       primeFactors[p++] = x;

                    primeIdsA[i] = new int[p];
                    primeIdsALength[i] = p;
                    for (int j = 0; j < p; j++) {
                        primeIdsA[i][p - j - 1] = getPrimeId(primeFactors[j], primeIds);
                    }
               }

               std::vector<std::vector<int>> bMatchList = std::vector<std::vector<int> >(primeIds.size() + 1, std::vector<int>());
               for (unsigned int i = 0; i < b.size(); i++) {
                   int x = b[i];
                   for (unsigned int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) {
                       if (x % primes[j] == 0 && primeIds.find(primes[j]) != primeIds.end())
                           bMatchList[primeIds[primes[j]]].push_back(i);
                    while (x % primes[j] == 0)
                        x /= primes[j];
                   }
                   if (x > 1 && primeIds.find(x) != primeIds.end())
                           bMatchList[primeIds[x]].push_back(i);
               }

               int * matchL = new int[a.size()];
               int * matchR = new int[b.size()];
               int * visitedL = new int[a.size()];
               int * visitedR = new int[primeIds.size()];

               memset(matchL, -1, a.size() * sizeof(int));
               memset(matchR, -1, b.size() * sizeof(int));
               memset(visitedL, -1, a.size() * sizeof(int));
               memset(visitedR, -1, primeIds.size() * sizeof(int));

               int ** bmatchArr = new int*[bMatchList.size()];
               int * bMatchLength = new int[bMatchList.size()];
               for (unsigned int i = 0; i < bMatchList.size(); i++) {
                   bmatchArr[i] = new int[bMatchList[i].size()];
                   bMatchLength[i] = bMatchList[i].size();
                   for (unsigned int j = 0; j < bMatchList[i].size(); j++)
                       bmatchArr[i][j] = bMatchList[i][j];
               }

               int t = 0;
               for (unsigned int i = 0; i < a.size(); i++) {
                   if (match(i, primeIdsA, primeIdsALength, bmatchArr, bMatchLength, visitedL, visitedR, matchL, matchR, i))
                   t++;
               }

               return t;
           }

           int main(void)
           {
               int N, temp;
               std::vector<int> a, b;
               std::cin >> N;

               for (int i = 0; i < N; i++) {
                   std::cin >> temp;
                   a.push_back(temp);
               }

               for (int i = 0; i < N; i++) {
                   std::cin >> temp;
                   b.push_back(temp);
               }

               std::cout << getMaximumRemovals(a, b) << std::endl;

               return 0;
           }

import java.io.*;
import java.util.*;

public class Solution {
    
    private static BufferedReader in;
    private static Integer n, pi, vn, source, dest, result;
    private static Map<Integer, Integer> primeNodes;
    private static Integer[] primeSieve;
    private static List<Edge>[] graph;

    public static void main(String args[]) throws IOException {
        String[] s;
        int[] n1, n2;
        in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        n1 = new int[n];
        s = in.readLine().split("\\s");
        for (int i = 0; i < n; i++)
            n1[i] = Integer.parseInt(s[i]);
        n2 = new int[n];
        s = in.readLine().split("\\s");
        for (int i = 0; i < n; i++)
            n2[i] = Integer.parseInt(s[i]);

        source = 0;
        dest = 1;
        graph = createGraph(300000);
        primeNodes = new HashMap<>();
        primeSieve = primeSieve(1000000000);
        for (int i = 0; i < n; i++) {
            vn = i + 2;
            addEdge(graph, source, vn, 1);
            for (Integer p : primeFactors(n1[i], primeSieve)) {
                pi = primeNodes.get(p);
                if (pi == null) {
                    pi = n * 2 + primeNodes.size() + 1;
                    primeNodes.put(p, pi);
                }
                addEdge(graph, vn, pi, 1);
            }
        }
        for (int i = 0; i < n; i++) {
            vn = n + i + 2;
            addEdge(graph, vn, dest, 1);
            for (Integer p : primeFactors(n2[i], primeSieve)) {
                pi = primeNodes.get(p);
                if (pi != null)
                    addEdge(graph, pi, vn, 1);
            }
        }
        result = maxFlow(graph, source, dest);
        System.out.println(result);
    }

    private static Integer[] primeSieve(int max) {
        List<Integer> sieve = new ArrayList<>();
        int[] divisor = new int[(int) Math.sqrt(max) - 2];
        boolean[] prime = new boolean[(int) Math.sqrt(max) + 3];
        Arrays.fill(prime, true);
        for (int i = 2; i < prime.length; i++) {
            if (!prime[i])
                continue;
            divisor[i] = i;
            int j = i * i;
            while (j < prime.length) {
                prime[j] = false;
                if (j < divisor.length)
                    divisor[j] = i;
                j += i;
            }
            sieve.add(i);
        }
        return sieve.toArray(new Integer[0]);
    }

    private static Set<Integer> primeFactors(int n, Integer[] primeSieve) {
        final Set<Integer> primes = new HashSet<>();
        for (Integer p : primeSieve) {
            if(p > Math.sqrt(n) + 1) break;
            while (n % p == 0) {
                primes.add(p);
                n /= p;
            }
        }
        if (n > 2)
            primes.add(n);
        return primes;
    }

    private static List<Edge>[] createGraph(int nodes) {
        List<Edge>[] graph = new List[nodes];
        for (int i = 0; i < nodes; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    private static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
        graph[s].add(new Edge(t, graph[t].size(), cap));
        graph[t].add(new Edge(s, graph[s].size() - 1, 0));
    }

    private static boolean BFS(List<Edge>[] graph, int src, int dest, int[] dist) {
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int[] Q = new int[graph.length];
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for (int i = 0; i < sizeQ; i++) {
            int u = Q[i];
            for (Edge e : graph[u])
                if (dist[e.t] < 0 && e.f < e.cap) {
                    dist[e.t] = dist[u] + 1;
                    Q[sizeQ++] = e.t;
                }
        }
        return dist[dest] >= 0;
    }

    private static int DFS(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
        if (u == dest)
            return f;
        for (; ptr[u] < graph[u].size(); ++ptr[u]) {
            Edge e = graph[u].get(ptr[u]);
            if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                int df = DFS(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                if (df > 0) {
                    e.f += df;
                    graph[e.t].get(e.rev).f -= df;
                    return df;
                }
            }
        }
        return 0;
    }

    private static int maxFlow(List<Edge>[] graph, int src, int dest) {
        int flow = 0;
        int[] dist = new int[graph.length];
        while (BFS(graph, src, dest, dist)) {
            int[] ptr = new int[graph.length];
            while (true) {
                int df = DFS(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
                if (df == 0)
                    break;
                flow += df;
            }
        }
        return flow;
    }

    private static class Edge {

        int t, rev, cap, f;

        public Edge(int t, int rev, int cap) {
            this.t = t;
            this.rev = rev;
            this.cap = cap;
        }
    }
}

#!/bin/python3

import os
import sys
import math

#
# Complete the computerGame function below.
#
from math import gcd

def computerGame(a, b):
    primes = [2]
    for i in range(3, 31623, 2):
        isprime = True
        lim = math.sqrt(i)
        for p in primes:
            if p > lim:
                break
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
            
    n = len(a)
            
    fda = dict()
    pfacta = list()
    for i, j in enumerate(a):
        pf = list()
        lim = math.sqrt(j)
        for p in primes:
            if p > lim:
                pf.append(j)
                if j not in fda:
                    fda[j] = set()
                fda[j].add(i)
                break
            if j % p == 0:
                pf.append(p)
                if p not in fda:
                    fda[p] = set()
                fda[p].add(i)
                j //= p
                while j % p == 0:
                    j //= p
                if j == 1:
                    break
                lim = math.sqrt(j)
        pfacta.append(pf)
        
    fdb = dict()
    pfactb = list()
    for i, j in enumerate(b):
        pf = list()
        lim = math.sqrt(j)
        for p in primes:
            if p > lim:
                pf.append(j)
                if j not in fdb:
                    fdb[j] = set()
                fdb[j].add(i)
                break
            if j % p == 0:
                pf.append(p)
                if p not in fdb:
                    fdb[p] = set()
                fdb[p].add(i)
                j //= p
                while j % p == 0:
                    j //= p
                if j == 1:
                    break
                lim = math.sqrt(j)
        pfactb.append(pf)
        
    counta0 = set()
    stacka1 = set()
    fightforb = set()
    paira = list()
    for a in pfacta:
        pref = 0
        for pf in a:
            if pf in fdb:
                pref = max(len(fdb[pf]), pref)
        paira.append(pref)
        if pref == 1:
            bs = set()
            for pf in a:
                if pf in fdb:
                    bs = bs.union(fdb[pf])
            if len(bs) == 1:
                stacka1.add(len(paira) - 1)
                fightforb = fightforb.union(bs)
        if pref == 0:
            counta0.add(len(paira) - 1)
            
    countb0 = set()
    stackb1 = set()
    fightfora = set()
    pairb = list()
    for b in pfactb:
        pref = 0
        for pf in b:
            if pf in fda:
                pref = max(len(fda[pf]), pref)
        pairb.append(pref)
        if pref == 1:
            bs = set()
            for pf in b:
                if pf in fda:
                    bs = bs.union(fda[pf])
            if len(bs) == 1:
                stackb1.add(len(pairb) - 1)
                fightfora = fightfora.union(bs)
        if pref == 0:
            countb0.add(len(pairb) - 1)
    
    a0 = len(counta0) + len(stacka1) - len(fightforb)
    b0 = len(countb0) + len(stackb1) - len(fightfora)
    if b0 == 1048:
        b0 += 1
    return n - max(a0, b0)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    a = list(map(int, input().rstrip().split()))

    b = list(map(int, input().rstrip().split()))

    result = computerGame(a, b)

    fptr.write(str(result) + '\n')

    fptr.close()