找出给定集合的所有子集的最小公倍数之和

Question

给定：集合A = {a0, a1, ..., aN-1}（1 ≤ N ≤ 100），其中 2 ≤ ai ≤ 500。

问题：找出所有大小至少为2的A子集的最小公倍数(LCM)之和。

对于一个集合B = {b0, b1, ..., bk-1}，它的最小公倍数LCM定义为最小整数Bmin，使得对于所有0 ≤ i < k，都有bi | Bmin。

例子：

假设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) 子集计算最小公倍数，这对于相当大的 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]，其中i可以是0到100。然而，由于dp[i]依赖于dp[i-1]，所以dp[70000][2]就足够了。这将复杂度降至n * 70000，是可行的。

我有以下具体问题：

• 这些状态是什么意思？
• dp 是否代表动态规划，如果是，正在解决什么递归关系？
• 如何从 dp[i-1] 计算出 dp[i] ？
• 为什么大质数不会对状态数量产生贡献？每个大质数只出现 0 或 1 次。这些质数的状态数量不应该乘以 2（导致状态空间不可行）吗？

_{^*原问题描述可以在 this source (problem F) 中找到。此问题是该描述的简化版本。}

- MasterMind

---

@PhamTrung，请问"state"是什么意思，dp[state][i]又代表什么，以及如何将其转化为dp[f(state)][i] = g( dp[state][i-1] )的形式。 - Ralor

@MasterMind，我能理解你对这个问题的沮丧，因为自从我看到你的问题后，它也一直萦绕在我的脑海中 :) 我试图重新表述一下这个问题，以便（希望）能够吸引更多的答案。我认为我尽可能地保持了你原来问题的核心，但你能否请确认一下呢？ - Vincent van der Weele

@VincentvanderWeele 非常感谢，你真的完全理解我的意思。你所做的修改非常棒，你提出的问题是核心和问题的关键。再次感谢。 - MasterMind

Stack Overflow不是一个让别人帮你做作业的网站... - Rob Baillie

Answer 1

这篇文章的第一部分似乎很有用，但第二部分比较模糊（也许没有帮助；我宁愿完成这个回答，而不是弄清楚它）。

假设输入由成对不同的质数组成，例如2、3、5和7。那么答案（对于求所有集合的总和，其中0个整数的LCM为1）为

(1 + 2) (1 + 3) (1 + 5) (1 + 7),

因为子集的最小公倍数正好等于这里的乘积，所以只需将其相乘即可。

让我们放宽质数两两不同的限制。如果我们有一个输入，如2, 2, 3, 3, 3和5，则乘法看起来像：

(1 + (2^2 - 1) 2) (1 + (2^3 - 1) 3) (1 + (2^1 - 1) 5),

由于数字2出现了两次，数字3出现了三次，数字5出现了一次。例如，只考虑数字3的集合，有2^3 - 1种选择包含数字3的子集，以及1种选择空集的方法。

如果一个质数小于等于19，则称其为小质数，反之则称其为大质数。请注意，500或更少的整数最多只能被一个大质数（带重复）整除。小质数更棘手。我们要做的是计算LCM的每个可能的小部分（即约70,000种状态之一）的总和，通过放弃不能将这样的LCM除以其他整数并仅保留大质数（或1）来导出问题。

例如，如果输入是2、30、41、46和51，并且状态是2，则将2保留为1，将30（= 2 * 3 * 5；3和5是小的）舍弃，将41保留为41（41很大），将46保留为23（= 2 * 23；23很大），并舍弃51（= 3 * 17；3和17是小的）。现在，我们使用先前描述的技术计算LCM的总和。使用容斥原理来消除其小部分恰好被状态正确地整除而不是完全相等的子集。也许我稍后会提供一个完整的例子。

- David Eisenstat

---

FYI：看起来，OP 特别询问第二部分... 如果你不理解某些内容，这并不意味着它是无用的。 - artur grzesiak

@arturgrzesiak 不太客气地说，我认为这是错误的，但它如此模糊，以至于可以说它甚至不是错误的。 - David Eisenstat

如果您能更具体地说明如何在这种情况下使用包含排除法，那将仍然非常有帮助，但是这个答案提供了许多有用的指示。 - Vincent van der Weele

Answer 2

讨论

在阅读实际比赛说明(第10或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（因为该组件的故障时间已经计算过一次）。

要从每个组件c的dp[i][n-1]填充dp[i][n]：

• 对于每个i，将dp[i][n-1]复制到dp[i][n]中。
• 将dp[T(c)][n]加1。
• 对于每个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]的配置数，因此一旦引入新组件，我们应该记录那么多的新故障时间。

为什么大质数没有增加状态数量？

它们中的每一个要么出现0次，要么出现1次。这些质数的数量不应该乘以2（导致状态空间非可行）吗？

您是正确的。但是，解决方案草图指出具有大质数的数字以另一种（未指定的）方式进行处理。

如果我们确实包含它们会发生什么？我们需要表示的状态数量将爆炸成不切实际的数量。因此，作者以不同的方式处理这样的数字。请注意，如果小于或等于500的数字包含大于19的质数，则其他因数相乘为21或更少。这使得这些数字易于暴力破解，无需表格。

- Kaganar

---

我认为这个回答非常准确地回答了具体的问题。对于递归关系的部分，我觉得有点难以理解（我不确定你添加的上下文是否使它比仅仅解决抽象问题时更简单），但是它似乎是正确的。 - Vincent van der Weele

不可否认，我非常努力地保持与草图作者的措辞一致 -- 似乎作者在脑海中有一定的模式，并使用术语，即使它与手头的问题不匹配。所以我认为你很可能是对的 -- 我最终得到了两个世界中最糟糕的东西 -- 有些不正确的术语和解决问题的深奥方法。谢谢你让我看清了这一点 -- 这将帮助我改进未来的答案。 - Kaganar

Answer 3

这些状态是什么意思？

我认为这里的状态指的是数字是否在集合B = {b0，b1，...，bk-1}的LCM中。

dp代表动态规划吗？如果是，正在解决什么递归关系？

我相信解决方案草图中的dp代表动态规划。

如何从dp [i-1]计算dp [i]？

我们可以从先前的状态中推断出下一组LCM的状态。因此，我们只需要一个长度为2的数组，并来回切换。

为什么大质数不会对状态数量产生贡献？每个大质数都只出现0次或1次。这些质数的状态数量不应该乘以2（导致状态空间不可行）吗？

我们可以使用质因数分解和指数来表示数字。

这里是一个例子。

6 = (2^1)(3^1)(5^0) -> 使用“1 1 0”表示6

18 = (2^1)(3^2)(5^0) -> 使用“1 2 0”表示18

以下是使用质因数分解获取6和18的最小公倍数的方法：

LCM (6,18) = (2^(max(1,1)) (3^ (max(1,2)) (5^max(0,0)) = (2^1)(3^2)(5^0) = 18

2^9 > 500，3^6 > 500，5^4 > 500，7^4>500，11^3 > 500，13^3 > 500，17^3 > 500，19^3 > 500

我们可以使用质数2、3、5、7、11、13、17、19的指数计数来表示集合B = {b0，b1，...，bk-1}中的LCM，对于给定的集合A = {a0，a1，...，aN-1}（1≤N≤100），其中2≤ai≤500。

9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 <= 70000，因此我们只需要两个dp[9][6][4][4][3][3][3][3]来跟踪所有LCM的状态。所以，dp[70000][2]就足够了。

我编写了一个小型的C++程序，以说明如何获取给定集合A = {a0，a1，...，aN-1}（1≤N≤100），其中2≤ai≤500的LCMs之和。在解决方案草图中，我们需要循环遍历最大可能的70000个LCMs。

int gcd(int a, int b) {
    int remainder = 0;
    do {
        remainder = a % b;
        a = b;
        b = remainder;
    } while (b != 0);
    return a;
}

int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return (a * b) / gcd(a, b);
}


int sum_of_lcm(int A[], int N) {

    // get the max LCM from the array
    int max = A[0];
    for (int i = 1; i < N; i++) {
        max = lcm(max, A[i]);
    }
    max++;

    //
    int dp[max][2];
    memset(dp, 0, sizeof(dp));
    int pri = 0;
    int cur = 1;

    // loop through n x 70000
    for (int i = 0; i < N; i++) {
        for (int v = 1; v < max; v++) {
            int x = A[i];
            if (dp[v][pri] > 0) {
                x = lcm(A[i], v);
                dp[v][cur] = (dp[v][cur] == 0) ? dp[v][pri] : dp[v][cur];
                if ( x % A[i] != 0 ) {
                    dp[x][cur] += dp[v][pri] + dp[A[i]][pri];
                } else {
                    dp[x][cur] += ( x==v ) ? ( dp[v][pri] + dp[v][pri] ) : ( dp[v][pri] ) ;
                }
            }
        }
        dp[A[i]][cur]++;
        pri = cur;
        cur = (pri + 1) % 2;
    }

    for (int i = 0; i < N; i++) {
        dp[A[i]][pri] -= 1;
    }
    long total = 0;
    for (int j = 0; j < max; j++) {
        if (dp[j][pri] > 0) {
            total += dp[j][pri] * j;
        }
    }
    cout << "total:" << total << endl;

    return total;
}



int test() {
    int a[] = {2, 6, 7 };
    int n = sizeof(a)/sizeof(a[0]);
    int total = sum_of_lcm(a, n);
    return 0;
}

Output
total:104

- stones333

---

尝试使用输入[2^8, 3^5, ..., 491, 499]运行您的示例代码。数组A的大小稍微超过70000... - Vincent van der Weele

这是一个关于计算LCM总和的DP示例，一种想法。 - stones333

Answer 4

状态比质数的幂多一个。你有小于2^8的数字，所以2的幂在[0..8]之间，共9个状态。其他状态同理。

"dp"很可能代表动态规划，但我不确定。

递归关系是问题的核心，通过自己解决问题来学到更多知识。从一些小而简单的例子开始。

对于大质数，尝试解决一个不使用它们（或它们的等价物）的简化问题，然后再将它们加回去，看看它们对最终结果的影响。

- rossum

---

我觉得这个答案解释了一切，但难点在于什么。建议解决方案的动态规划方面是什么？ - Teepeemm

@Teepeemm：确切地说，就像我所说的，“通过自己解决问题，你会学到更多。” - rossum

但是你的回答唯一增加的就是明确指出 9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 来自于质数的幂。除此之外（显而易见的？），这个回答没有任何添加。 - Teepeemm

@Teepeemm：再读一遍，“从一些小而简单的例子开始。” - rossum

我完全同意你的观点，自己摸索是最好的学习方式。但是你怎么知道 OP 没有尝试过任何小而简单的例子呢？就目前而言，这不是问题的答案，只是一条评论。 - Vincent van der Weele