两个以上数字的最小公倍数

Question

我想找出两个以上数字的最小公倍数（LCM）。我知道 lcm(a,b) = (a * b) / gcd(a,b) 的公式。比方说，我有一个数字数组：[2, 6, 8, 13] 并且 lcm 应该模 M = 1000000007.

我看过下面的代码来计算多个数字的 LCM，但我不明白这两个循环的计算是如何进行的。

int arr[] = {2, 6, 8, 13}, n = 4
long long int ans=1;
long long int M=1000000007;
for(int i=0;i<n;i++)   // Calculating LCM
{
    for(int j=i+1;j<n;j++)
    {
        arr[j]=arr[j]/__gcd(arr[i],arr[j]);
    }
    ans=((ans%M)*(arr[i]%M))%M;
}
return (ans)%M;

谁能帮我理解上面代码中的LCM计算？

Answer 1

知道`gcd(a, b)`表示`a`和`b`共有的所有质因数的乘积，那么`a / gcd(a,b)`有什么意义呢？

a / gcd(a, b) 等于 a 中不在 b.

中的质因数

因此，当您将该数量乘以 b 时，您会得到 b 的所有质因数与 a 的所有质因数的乘积不在 b 中。这正是lcm(a, b).

让我们将其扩展到任意数量的整数。

lcm(a, b) 是 a 乘以不在 a 中的 b 的所有质因数或：

a * (b / gcd(a, b)) = (a * b) / gcd(a, b)

很简单，你已经知道了。

但是如果我们有第三个数字，lcm(a, b, c) 是 b 的所有质因数的 a 倍，而不是 a 的所有质因数的乘积38=] 既不在 a 也不在 b。好吧，第一部分很简单，和上面一样：

lcm(a, b, c) = lcm(a, b) * (all the prime factors of c in neither a nor b)

如何计算 all the prime factors of c in neither a nor b 一开始可能并不明显，但并不过分复杂：

all the prime factors of c in neither a nor b = c / (gcd(a, c) * gcd(b, c))

也就是说

lcm(a, b, c) = lcm(a, b) * c / (gcd(a, c) * gcd(b, c))
lcm(a, b, c) = (a * b * c) / (gcd(a, b) * gcd(a, c) * gcd(b, c))

现在，您可以轻松概括：

lcm(a[0], ..., a[N]) = prod(a[0], ..., a[N]) / pairwise_gcd(a[0], ..., a[N])

但更相关的公式是递归版本：

lcm(a[0], ..., a[N]) = lcm(a[0], ..., a[N-1]) * a[N] / (gcd(a[0], a[N]) * ... * gcd(a[N-1], a[N]))

或：

lcm(a[0], ..., a[N]) = a[0] * lcm(a[1] / gcd(a[0], a[1]), ..., a[N] / gcd(a[0], a[N]))

这是将您的代码片段转换为伪代码的尝试

将此与数组上 lcm 的最后定义进行比较，我试图使它们看起来相似。

given int array = arrayOfNums
int product := 1
for number in arrayOfNums
    remove all prime factors of number from all subsequent array elements
    product = product * number
product is now the lcm of arrayOfNums

希望这不会太混乱；我承认这可能不是一个很好的解释，但它是一个起点。如果还有什么不清楚的，请告诉我。

两个以上数字的最小公倍数

Least common multiple for more than two numbers

c++

lcm

知道`gcd(a, b)`表示`a`和`b`共有的所有质因数的乘积，那么`a / gcd(a,b)`有什么意义呢？

让我们将其扩展到任意数量的整数。

这是将您的代码片段转换为伪代码的尝试

两个以上数字的最小公倍数

Least common multiple for more than two numbers

c++

lcm

知道gcd(a, b)表示a和b共有的所有质因数的乘积，那么a / gcd(a,b)有什么意义呢？

让我们将其扩展到任意数量的整数。

这是将您的代码片段转换为伪代码的尝试

知道`gcd(a, b)`表示`a`和`b`共有的所有质因数的乘积，那么`a / gcd(a,b)`有什么意义呢？