489C

Description

Given two set of integers. Totally, $n$ integers. There are $m$ edges connecting some integers from one set to the other. ($1 \leq n,m \leq 100$)

One operation could reduce two integers which have a edge between them by a common factor. Output the maximum number of operations could be performed.

Tutorial

It is easy to know that each operation should use a prime factor, so that the answer could be maximized. For each prime number which is a factor of any of the integer in the set, we perform a maxflow. Each integer is a vertex in the network flow graph.

In the time of prime $p$, we add edges from the source to the integers in the first set with capacity of the number of $p$s that the integer contains. Likely, we add edges from the integers in the second set to the terminal.

Finally, we add up each maxflow which is the answer of the problem.

Solution

#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int MAX_N = 105;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef int F;
#define F_INF (1<<29)
#define MAXV 1000
#define MAXE 1000 // E*2!

F cap[MAXE],flow[MAXE];
int to[MAXE],_prev[MAXE],last[MAXV],used[MAXV],level[MAXV];

struct MaxFlow{
    int V,E;

    MaxFlow(int n){
    int i;
    V = n; E = 0;
    REP(i,V) last[i] = -1;
    }

    void add_edge(int x, int y, F f){
    cap[E] = f; flow[E] = 0; to[E] = y; _prev[E] = last[x]; last[x] = E; E++;
    cap[E] = 0; flow[E] = 0; to[E] = x; _prev[E] = last[y]; last[y] = E; E++;
    }

    bool bfs(int s, int t){
    int i;
    REP(i,V) level[i] = -1;
    queue <int> q;
    q.push(s); level[s] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(i=last[x];i>=0;i=_prev[i]) if(level[to[i]] == -1 && cap[i] > flow[i]) {q.push(to[i]); level[to[i]] = level[x] + 1;}
    }
    return (level[t] != -1);
    }

    F dfs(int v, int t, F f){
    int i;
    if(v == t) return f;
    for(i=used[v];i>=0;used[v]=i=_prev[i]) if(level[to[i]] > level[v] && cap[i] > flow[i]){
        F tmp = dfs(to[i],t,min(f,cap[i]-flow[i]));
        if(tmp > 0) {flow[i] += tmp; flow[i^1] -= tmp; return tmp;}
    }
    return 0;
    }

    F maxflow(int s, int t){
    int i;
    while(bfs(s,t)){
        REP(i,V) used[i] = last[i];
        while(dfs(s,t,F_INF) != 0);
    }
    F ans = 0;
    for(i=last[s];i>=0;i=_prev[i]) ans += flow[i];
    return ans;
    }

};

int n, m;
int f[MAX_N];
int odd[MAX_N], even[MAX_N];

int main()
{
    //input
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", f + i);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        if (b & 1)
        {
            swap(a, b);
        }
        odd[i] = a;
        even[i] = b;
    }

    //work
    set<int> s;
    for (int i = 0; i < n; i++)
    {
        int temp = f[i];
        for (int j = 2; j * j <= temp; j++)
        {
            if (temp % j == 0)
            {
                s.insert(j);
            }
            while (temp % j == 0)
            {
                temp /= j;
            }
        }
        if (temp > 1)
        {
            s.insert(temp);
        }
    }

    //flow
    int ans = 0;
    for (typeof(s.begin()) itr = s.begin(); itr != s.end(); itr++)
    {
        int factor = *itr;
        MaxFlow net = MaxFlow(n + 2);
        for (int i = 0; i < n; i++)
        {
            int cnt = 0;
            int temp = f[i];
            while (temp % factor == 0)
            {
                temp /= factor;
                cnt++;
            }
            if (i & 1)
            {
                net.add_edge(n, i, cnt);
            }else
            {
                net.add_edge(i, n + 1, cnt);
            }
        }
        for (int i = 0; i < m; i++)
        {
            net.add_edge(odd[i], even[i], F_INF);
        }
        ans += net.maxflow(n, n + 1);
    }
    printf("%d\n", ans);
    return 0;
}