algorithm - 求给定集合的所有子集的最小公倍数之和

Question

鉴于:套装A = {a0, a1, ..., aN-1} ( 1 ≤ N ≤ 100 )，与 2 ≤ ai ≤ 500 .

提问:求 A 的所有子集的所有最小公倍数 (LCM) 的总和大小至少为 2。

一套LCM B = {b0, b1, ..., bk-1}定义为最小整数 Bmin使得 bi | Bmin , 所有 0 ≤ i < k .

示例:

让 N = 3和 A = {2, 6, 7} ， 然后:

LCM({2, 6})      =    6
LCM({2, 7})      =   14
LCM({6, 7})      =   42
LCM({2, 6, 7})   =   42
----------------------- +
answer              104

天真的方法是简单地计算所有 O(2N) 的 LCM子集，这对于相当大的 N 是不可行的.

解决方案草图:

该问题是从比赛*中获得的，该比赛还提供了 solution sketch .这就是我的问题所在:我不明白暗示的方法。

解决方案如下(以一些小的固定语法问题为模):

The solution is a bit tricky. If we observe carefully we see that the integers are between 2 and 500. So, if we prime factorize the numbers, we get the following maximum powers:

 2 8  
 3 5
 5 3
 7 3
11 2
13 2
17 2
19 2

Other than this, all primes have power 1. So, we can easily calculate all possible states, using these integers, leaving 9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 states, which is nearly 70000. For other integers we can make a dp like the following: dp[70000][i], where i can be 0 to 100. However, as dp[i] is dependent on dp[i-1], so dp[70000][2] is enough. This leaves the complexity to n * 70000 which is feasible.

我有以下具体问题:

这些状态是什么意思？

是否dp代表动态规划，如果是这样，正在解决什么递推关系？

怎么样dp[i]从 dp[i-1] 计算?

为什么大素数对状态数没有贡献？它们中的每一个都发生在 0或 1次。如果状态数不乘以 2对于这些质数中的每一个(再次导致不可行的状态空间)？

*原始问题描述可以从this source找到(问题F)。这个问题是该描述的简化版本。

Answer 1

讨论

在阅读了实际的比赛描述 (page 10 or 11) 和解决方案草图后，我不得不得出结论，解决方案草图的作者在他们的写作中非常不准确。

如果通过公平抛硬币随机选择组件，则高级问题是计算预期生命周期。这就是导致计算所有子集的 LCM 的原因——所有子集都有效地表示样本空间。您最终可以得到任何可能的组件集。设备的故障时间基于设备的 LCM。因此，预期生命周期是所有集合的 LCM 的平均值。

请注意，这应该包括只有一个项目的集合的 LCM(在这种情况下，我们假设 LCM 是元素本身)。解决方案草图似乎在破坏，也许是因为他们以不太优雅的方式处理它。

这些状态是什么意思？

草图作者只使用了两次状态这个词，但显然设法转换了含义。在第一次使用状态这个词时，他们似乎在谈论可能的组件选择。在第二次使用中，他们可能会谈论可能的故障时间。他们可能混淆了这个术语，因为他们的动态规划解决方案从单词的一种使用中初始化值，而递归关系则源于另一种。

dp 代表动态规划吗？

我会说要么是这样，要么是巧合，因为解决方案草图似乎在很大程度上暗示了动态规划。

如果是这样，正在解决什么递推关系？如何从 dp[i-1] 计算 dp[i]？

我所能想到的是，在他们的解决方案中，声明 i表示故障时间，T(i) ，加上这次失败的次数已经统计，dp[i] .结果总和将是所有 dp[i] * T(i) 的总和.
dp[i][0]然后将是仅计算第一个组件的故障时间。 dp[i][1]然后将是为第一个和第二个组件计算的故障时间。 dp[i][2]将用于第一，第二和第三。等等..

初始化 dp[i][0]除 dp[T(c)][0] 外均为零(其中 c 是考虑的第一个组件)应该是 1(因为到目前为止该组件的故障时间已被计算一次)。

填充 dp[i][n]来自 dp[i][n-1]每个组件c :

每个i , 复制 dp[i][n-1]进入 dp[i][n] .

加 1 到 dp[T(c)][n] .

每个i , 添加 dp[i][n-1]至 dp[LCM(T(i), T(c))][n] .

这是在做什么？假设您知道您有时间失败 j ，但您添加了一个故障时间为 k 的组件.无论您之前拥有什么组件，新的失败时间都是 LCM(j, k) .这是因为对于两组 A和 B , LCM(A union B} = LCM(LCM(A), LCM(B)) .

类似地，如果我们考虑到失败时间 T(i)以及我们新组件的失效时间 T(c) ，由此产生的故障时间为 LCM(T(i), T(c)) .请注意，我们记录的失败时间为 dp[i][n-1]配置，因此一旦引入新组件，我们应该记录许多新的失败次数。

为什么大素数对状态数没有贡献？

Each of them occurs either 0 or 1 times. Should the number of states not be multiplied by 2 for each of these primes (leading to a non-feasible state space again)?

你是对的，当然。但是，解决方案草图指出以另一种(未指定的)方式处理具有大素数的数字。

如果我们确实包含它们会发生什么？我们需要表示的状态数量会爆炸成一个不切实际的数字。因此，作者对这些数字的解释不同。请注意，如果小于或等于 500 的数包含大于 19 的素数，则其他因数乘以等于或小于 21。这使得这些数字适合暴力破解，不需要表格。