C++ 中数组中所有数字的 LCM

Question

我遇到了这段代码来计算数组中所有数字的最小公因数，但无法理解所使用的算法。这里用来计算设定位数的__builtin_popcount有什么用？

pair<long long, int> pre[200000];
long long a[25], N;
long long trunc_mul(long long a, long long b)
{
    return a <= INF / b ? a * b : INF;
}
void compute()
{
    int limit = 1 << N;
    limit--;
    for (int i = 1; i <= limit; i++)
    {
        long long lcm = 1;
        pre[i].second = __builtin_popcount(i);
        int k = 1;
        for (int j = N - 1; j >= 0; j--)
        {
            if (k&i)
            {
                lcm = trunc_mul(lcm / __gcd(lcm, a[j]), a[j]);
            }
            k = k << 1;
        }
        pre[i].first = lcm;
    }
    return;
}

Answer 1

您提供的截取代码最多提供 25 个数字。对于每个数字子集，它将它们的 LCM 计算成pre[i].first并将该子集中的数字计算成 pre[i].second 。子集本身表示为位掩码，因此要计算子集中的元素数，代码片段使用 __builtin_popcount .它与LCM的计算无关。

LCM 是使用一种相当标准的方法计算的：任何一组数字的 LCM 等于它们的乘积除以它们的 GCD。这正是这个截图所做的，使用内置的GCD函数__gcd。

k&i和k = k<<1部分是找出哪些数字属于由位掩码表示的集合。如果您不完全理解它，请尝试通过在一张纸上或在调试器中运行此循环来查看如果i = 0b11010会发生什么。您会注意到，k&i条件在第二次、第四次和第五次迭代中将为真，恰好是i在其二进制表示中具有 1 的位置。