arrays - 数组上的最大 "divide"操作

Question

给定一个 n 正整数数组 a[1], a[2], ..., a[n] 和 m 好的整数对 (i₁, j₁), (i₂, j₂ ), ...,⟩(i_m, j_m) 其中 1 ≤ i_k < j_k ≤ n ,n<=100 & m<=100

编辑:每个好的对 (ik, jk) 满足以下条件:ik + jk 是奇数且 1 ≤ ik < jk ≤ n。

在一个操作中，您可以执行一系列操作:取一个好的对 (i_k, j_k) 和一些整数 v (v > 1) , 它除以 a[i_k] 和 a[j_k] 和 divide v 两个数字。

确定您可以对给定数组顺序执行的最大 操作数。请注意，在所描述的操作中，一对可能会使用多次。

我的方法:

我首先对数组的每个数字进行质因数分解。给定一对 (ik,jk)，我们可以将两个数 A[ik] 和 A[jk] 除以它们的公共(public)质数幂即如果 A[ik]=2^5 * 3^4 和 A[jk]=2^3 * 3^7 那么我们可以将它们都除以 < em>2 一共 3 次 除以 3 总共 4 次。运算次数增加了最小的公共(public)质数幂，即 7。

然后可以将操作总数视为所有给定的好对的所有公共(public)质数幂的总和。

但是我的代码失败以下测试用例:

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 以及解决这个问题的方法。

PS:题目是codeforces Div2 Round 284的E题。

问题链接: http://codeforces.com/contest/499/problem/E

Answer 1

这个问题可以通过找到最大值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}}.

以边{A2c, B2a}为例的意思是，我们将标记为A和B的数组项进行划分通过 2。操作顺序无关紧要。

现在，有找到最大一般匹配的算法，但它们很复杂，令我惊讶的是编程竞赛会采用它们。事实证明，您遗漏了一个重要的约束条件，即好对的总和为奇数，这保证了该图将是二分的，因此适用于更简单的算法。根据实例的外观，从二分匹配切换到最大流也可能有利可图，例如，A 的 2 因子允许五个顶点和六个边 和 B 被三个容量单位的两个顶点和一条边代替。