给定一个n正整数数组a[1]，a[2]，…，a[n]和m好整数对（i1，j1），（i2，j2），…，（im，jm），其中1≤ikn编辑：每对好的（ik，jk）满足以下条件：ik+jk是奇数，1≤ik在一个操作中，您可以执行一系列操作：
取其中一对（ik，jk）和一个整数v（v>1），它将a[ik]和a[jk]分开，并将两个数除以v。
确定可在给定数组上顺序执行的最大操作数。注意，在所描述的操作中，一对可以多次使用。
我的方法：
我首先对数组的每个数字进行第一素数分解。
给定一个好的对（ik，jk），我们可以将a[ik]和a[jk]除以它们的共同素数幂，即如果A[ik]=2^5 * 3^4和A[jk]=2^3 * 3^7，那么我们可以将它们除以2，共3次，再除以3，共4次。操作数增加了公共素数幂的最小值，即增加了7。
然后，可以将运算的总数作为给定的所有好对的所有公共素数幂的和。
但是，对于以下测试用例，我的代码失败了：
N=10
M=9
A[]=67108864 8 2 131072 268435456 256 16384 128 8 128
Good Pairs :
4 9
5 10
6 9
9 10
1 4
3 8
8 9
1 2
4 5
数组中每个元素的不同幂为2。
就2的幂而言，数组可以写成：
B[]= 26 3 1 17 28 8 14 7 3 7 //A[i] = 2^B[i]选择好的一对，减去2的公幂，我的答案是：
26 3 1 14 28 8 14 7 0 7 ans 3
26 3 1 14 21 8 14 7 0 0 ans 10
26 3 1 14 21 8 14 7 0 0 ans 10
26 3 1 14 21 8 14 7 0 0 ans 10
12 3 1 0 21 8 14 7 0 0 ans 24
12 3 0 0 21 8 14 6 0 0 ans 25
12 3 0 0 21 8 14 6 0 0 ans 25
9 0 0 0 21 8 14 6 0 0 ans 28
9 0 0 0 21 8 14 6 0 0 ans 28
处理好每一对，我的代码给出的答案是28。
然而正确答案是31。我需要帮助来理解输出是如何变成31的，以及解决这个问题的方法。
注：问题是第284轮第2分队的问题E。
链接到问题：
http://codeforces.com/contest/499/problem/E
最佳答案
这个问题可以通过在下面的图中找到最大值matching来解决。对于每个数组值x，对于具有多重性的x的每个素因子，创建一个新顶点例如，如果x=12，则创建两个2顶点和一个3顶点。使对应于数组值的相同素因子的顶点对之间的边形成一个良好的对例如，在输入端
A B C # array indexes
8 12 18 # array
A B # good pairs
B C,
图有顶点
{A2a, A2b, A2c, B2a, B2b, B3, C2, C3a, C3b}
和边缘
{{A2a, B2a}, {A2a, B2b}, {A2b, B2a}, {A2b, B2b}, {A2c, B2a}, {A2c, B2b},
{B2a, C2}, {B2b, C2},
{B3, C3a}, {B3, C3b}}.
以edge
{A2c, B2a}为例，其含义是我们将标记为A和B的数组项除以2。操作顺序无关紧要。现在，有一些算法来寻找最大的一般匹配，但是它们很复杂，我很惊讶一个编程竞赛会给它们带来特色。事实证明，您忽略了一个重要的约束，即好的对和为奇数，这保证了图是二分的，因此可以使用更简单的算法。取决于实例的样子，从二部匹配切换到最大流也可能是有利可图的，这使得例如“CC＞和
2的A因子的五个顶点和六个边缘被两个顶点和一个具有三个单位容量的边替换。