比赛原题第二弹，网络流+数论。

题目描述

        You have written on a piece of paper an array of n positive integers $a[1], a[2], …, a[n]$ and $m$ good pairs of integers $(i_1, j_1), (i_2, j_2), …, (i_m, j_m)$. Each good pair $(i_k, j_k)$ meets the following conditions: $i_k + j_k$ is an odd number and $1 ≤ i_k < j_k ≤ n$.
        In one operation you can perform a sequence of actions:

  • take one of the good pairs $(i_k, j_k)$ and some integer $v (v > 1)$, which divides both numbers $a[i_k]$ and $a[j_k]$;
  • divide both numbers by $v$, i. e. perform the assignments: $\frac {a_{ik}} {v}$ and$\frac {a_{jk}} {v}$ .
    Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.

输入输出格式

输入格式

        The first line contains two space-separated integers $n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100)$.
        The second line contains n space-separated integers $a[1], a[2], …, a[n] (1 ≤ a[i] ≤ 10^9)$ — the description of the array.
        The following $m$ lines contain the description of good pairs. The k-th line contains two space-separated integers $i_k, j_k$ ($1 ≤ i_k < j_k ≤ n$, $i_k + j_k$ is an odd number).
        It is guaranteed that all the good pairs are distinct.

输出格式

        Output the answer for the problem.

输入输出样例

Sample intput1

3 2
8 3 8
1 2
2 3

Sample output2

0

Sample input2

3 2
8 12 8
1 2
2 3

Sample output2

2

题解

        由于$i_k+j_k$为奇数，这说明每一对数只能一个来自奇数位，一个来自偶数位，这样将奇偶数位分开，在上面连线，可以得到一个二分图。
        对每一个数作质因数分解，最多可以拆出10个互异的质因子。于是将每一个数都拆成10个点，每一个点代表这个数的某一个质因子。之后就可以用网络流解决了。建图如下：

  • $S->V(x,y)$，$x$为奇数。这里$V(x,y)$是第$x$个数的第$y$个质因子对应的点编号，其容量限制设置为第$x$个数含有这个质因子的数目。
  • $V(x,y)->T$，$x$为偶数，理解同上。
  • 对于一对数$(i_k,j_k)$，我们从奇数位出发向偶数位连边。如果两个数$a_{ik}$与$a_{jk}$存在相同的质因子，那么连接这两个点，容量限制为无穷大。

        对于这个图的理解：源点与汇点限制质因子数目，中间的边代表转移，每有一个流流过便代表一次合法的操作。最后在这个图上跑一遍最大流即可，答案就是最大流量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

#define JS(x) ((x)%2?(x)/2+1:(x)/2)
#define ID(x, y) ((x)%2==0?(JS(n)*10+((x)/2-1)*10+y):(((x)/2)*10+y))
#define inf (1<<28)
#define S 0
#define T (n%2?ID(n-1,10)+1:ID(n,10)+1)
using namespace std;
struct Edge {
    int next, to, v;
} edge[500000];
int head[1500], n, m, op[150], dep[1500];
vector<int> vvp[150], num[150];
queue<int> que;

inline void add(int x, int y, int v) {
//    cout << x << " " << y << " " << v << endl;
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

inline int BFS() {
    for (int i = S; i <= T; i++)dep[i] = inf;
    while (!que.empty())que.pop();
    dep[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == T)return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dep[edge[i].to] == inf)dep[edge[i].to] = dep[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

int DFS(int x, int limit) {
    if (x == T || limit == 0)return limit;
    int p, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (dep[edge[i].to] == dep[x] + 1 && (p = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= p, edge[i ^ 1].v += p, limit -= p, flow += p;
            if (limit == 0)break;
        }
    }
    return flow;
}

int main() {
    memset(head, -1, sizeof(head)), cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> op[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j * j <= op[i]; j++) {
            if (op[i] % j == 0) {
                vvp[i].push_back(j), num[i].push_back(0);
                while (op[i] % j == 0)num[i][num[i].size() - 1]++, op[i] /= j;
            }
        }
        if (op[i] != 1) vvp[i].push_back(op[i]), num[i].push_back(1);
        for (int j = 0; j < vvp[i].size(); j++) {
            if (i % 2)add(S, ID(i, j + 1), num[i][j]);
            else add(ID(i, j + 1), T, num[i][j]);
        }
    }
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        if (x % 2 == 0)swap(x, y);
        for (int j = 0; j < vvp[x].size(); j++) {
            for (int z = 0; z < vvp[y].size(); z++)if (vvp[x][j] == vvp[y][z])add(ID(x, j + 1), ID(y, z + 1), inf);
        }
    }
    int ans = 0;
    while (BFS())ans += DFS(S, inf);
    cout << ans;
    return 0;
}