找到的一组给定的所有子集的最小公倍数的总和 [英] Find the sum of least common multiples of all subsets of a given set

问题描述

考虑：设置 A = {A <子> 0 ，一个<子> 1 ，...，A <子> N-1 } （ 1当量; N＆当量; 100 ），用 2当量;一个<子>我＆当量; 500 。

问：找到 A 的所有子集的大小至少为2的所有最小公倍数（LCM）的总和。

一组的LCM B = {B 0 ，B 1 ，...，B <子> K-1 } 被定义为最小整数 B <子>分 ，使得 B <子>我 |乙<子>分 ，所有 0当量; I＆LT;氏/ code>。

示例：

让 N = 3 和 A = {2，6，7} ，那么：

  LCM（{2,6}）= 6
LCM（{2,7}）= 14
LCM（{6,7}）= 42
LCM（{2，6,7}）= 42
----------------------- +
回答104
 

在幼稚的方法是简单地计算LCM所有 0（2 N ）子集，它不是相当大的可行 N 。

---

解决方案草图：

该问题是由竞争获得的 ^* ，这也提供了一个的解决方案草图。这是我的问题进来。我不明白的暗示方法

解决方案读取（模一些小的固定的语法问题）：

  

该解决方案是一个有点棘手。如果我们仔细观察，我们看到的整数介于 2 和 500 。所以，如果我们素比化的数字，我们得到如下最大功率：

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

  

除此之外，所有的素数有权力1。所以，我们可以很容易地计算出所有可能的状态，用这些整数，剩下 9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 状态，这是近 70000 。对于其他整数我们可以做出如下所示的DP： DP [70000] [I] ，其中我可 0 到 100 。然而，由于 DP [I] 依赖于 DP [I-1] ，所以 DP [70000] [2] 就足够了。这使得复杂 N * 70000 这是可行的。

我有以下具体问题：

• 什么是由这些国家的意思？
• 确实 DP 代表动态规划，如果有，是什么递推关系正在得到解决？
• 如何为 DP [I] 从 DP计算[I-1] ？
• 为什么大素数不利于国家的数量？他们每个人都出现任 0 或 1 次。如果各国无法通过 2 （再次导致非可行的状态空间）乘以每个这些素数？数量

<分> ^* 原来问题的说明可以发现，从的这个来源（问题F）。这个问题是这样的描述的简化版本。

解决方案

讨论

读取实际比赛说明（之后的 10页或11 ）和解决方案草图，我不得不得出结论的解决方案草图的作者是相当IM precise在他们的写作。

高层次的问题是计算的预期寿命，如果组件通过公平的掷硬币随机选择的。这是什么导致计算所有子集的LCM - 所有子集有效地重新present样本空间。你可能会与任何可能的一组组件。的失效时间为设备是基于组的LCM。因此，预期寿命是所有集合的LCM的平均

请注意，这应当包括套LCM的只有一个项目（在此情况下，我们会假定LCM的是元件本身）。该解决方案草图，似乎破坏，也许是因为他们处理在一个不太雅致的方式。

何谓这些国家？

草图笔者仅使用这个词的状态的两倍，但显然设法切换的意义。在第一次使用这个词的状态的出现，他们谈论的是一个可能的选择组件。在第二次使用，他们很可能在谈论可能的失败倍。它们可以得过且过这个术语，因为他们的动态规划解决方案，从一个使用这个词的初始化值和其他的递推关系茎。

DP是否代表了动态规划？

我会说不管是或这是一个巧合的解决方案草图似乎很大程度上意味着动态规划。

如果是这样，什么递推关系正在得到解决？如何DP [我]从DP [I-1]计算的？

所有我能想到的是，在他们的解决方案，状态的我重presents一个无故障时间， T（ⅰ），随着时代这个故障时间已经计数的数目， 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 ：

• 对于每个我，复制 DP [I] [N-1] 到 DP [I] [N] 。
• 添加1 DP [T（C）] [N] 。
• 对于每个我添加 DP [I] [N-1] 到 DP [LCM（T（I），T（C））] [N] 。

这是什么做的？假设你知道你有时间去失败Ĵ，但你添加的成分有时间的 K 。不管是什么成分，你收到了，新时失败是 LCM（J，K）。这是从一个事实，即两套 A 和 B ， LCM（A工会乙} = LCM（LCM（A），LCM（B））。

同样，如果我们考虑时间的失败T（I）和我们的新组件的时间的失败T（C） ，所产生的故障时间是 LCM（T（I），T（C））。请注意，我们记录了这次失败 DP [I] [N-1] 配置，所以我们应该记录下了许多新的次失败，一旦新的组件被引入。

为什么大素数不利于国家的数量？

  

每个他们的出现0或1次。应状态的数量不乘以2为每个这些素数（导致非可行状态空间再次）的

你是对的，当然。然而，该解决方案草图指出，与大质数号码在另一个（未指定）的方式进行处理。

如果我们确实有他们会发生什么？中的国号的，我们需要重新present就会爆炸成一个不切实际的数量。因此笔者反映了这些数字不同。注意，如果一个小于或等于500包括超过19素较大的其他因素相乘至21或更小。这使得这样的数字对于服从暴力破解，没有必要的表格。

Given: set A = {a0, a1, ..., aN-1} (1 ≤ N ≤ 100), with 2 ≤ ai ≤ 500.

Asked: Find the sum of all least common multiples (LCM) of all subsets of A of size at least 2.

The LCM of a setB = {b0, b1, ..., bk-1} is defined as the minimum integer Bmin such that bi | Bmin, for all 0 ≤ i < k.

Example:

Let N = 3 and A = {2, 6, 7}, then:

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

The naive approach would be to simply calculate the LCM for all O(2N) subsets, which is not feasible for reasonably large N.

---

Solution sketch:

The problem is obtained from a competition^*, which also provided a solution sketch. This is where my problem comes in: I do not understand the hinted approach.

The solution reads (modulo some small fixed grammar issues):

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.

I have the following concrete questions:

• What is meant by these states?
• Does dp stand for dynamic programming and if so, what recurrence relation is being solved?
• How is dp[i] computed from dp[i-1]?
• Why do the big primes not contribute to the number of states? 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)?

_{^*The original problem description can be found from this source (problem F). This question is a simplified version of that description.}

解决方案

Discussion

After reading the actual contest description (page 10 or 11) and the solution sketch, I have to conclude the author of the solution sketch is quite imprecise in their writing.

The high level problem is to calculate an expected lifetime if components are chosen randomly by fair coin toss. This is what's leading to computing the LCM of all subsets -- all subsets effectively represent the sample space. You could end up with any possible set of components. The failure time for the device is based on the LCM of the set. The expected lifetime is therefore the average of the LCM of all sets.

Note that this ought to include the LCM of sets with only one item (in which case we'd assume the LCM to be the element itself). The solution sketch seems to sabotage, perhaps because they handled it in a less elegant manner.

What is meant by these states?

The sketch author only uses the word state twice, but apparently manages to switch meanings. In the first use of the word state it appears they're talking about a possible selection of components. In the second use they're likely talking about possible failure times. They could be muddling this terminology because their dynamic programming solution initializes values from one use of the word and the recurrence relation stems from the other.

Does dp stand for dynamic programming?

I would say either it does or it's a coincidence as the solution sketch seems to heavily imply dynamic programming.

If so, what recurrence relation is being solved? How is dp[i] computed from dp[i-1]?

All I can think is that in their solution, state i represents a time to failure , T(i), with the number of times this time to failure has been counted, dp[i]. The resulting sum would be to sum all dp[i] * T(i).

dp[i][0] would then be the failure times counted for only the first component. dp[i][1] would then be the failure times counted for the first and second component. dp[i][2] would be for the first, second, and third. Etc..

Initialize dp[i][0] with zeroes except for dp[T(c)][0] (where c is the first component considered) which should be 1 (since this component's failure time has been counted once so far).

To populate dp[i][n] from dp[i][n-1] for each component c:

• For each i, copy dp[i][n-1] into dp[i][n].
• Add 1 to dp[T(c)][n].
• For each i, add dp[i][n-1] to dp[LCM(T(i), T(c))][n].

What is this doing? Suppose you knew that you had a time to failure of j, but you added a component with a time to failure of k. Regardless of what components you had before, your new time to fail is LCM(j, k). This follows from the fact that for two sets A and B, LCM(A union B} = LCM(LCM(A), LCM(B)).

Similarly, if we're considering a time to failure of T(i) and our new component's time to failure of T(c), the resultant time to failure is LCM(T(i), T(c)). Note that we recorded this time to failure for dp[i][n-1] configurations, so we should record that many new times to failure once the new component is introduced.

Why do the big primes not contribute to the number of states?

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)?

You're right, of course. However, the solution sketch states that numbers with large primes are handled in another (unspecified) fashion.

What would happen if we did include them? The number of states we would need to represent would explode into an impractical number. Hence the author accounts for such numbers differently. Note that if a number less than or equal to 500 includes a prime larger than 19 the other factors multiply to 21 or less. This makes such numbers amenable for brute forcing, no tables necessary.

这篇关于找到的一组给定的所有子集的最小公倍数的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！