math - n 个数模 1000000007 的 LCM

Question

我必须找到 n 个数字 MODULO 10^9+7 的 LCM。我的方法是找到两个数字的 LCM，然后对它们进行 MOD。然后取下一个元素的 LCM 和从上一次迭代中获得的答案并对它们进行 MOD。对所有元素都这样做。这是错误的吗？

Answer 1

是的，这是错误的。我一直在研究类似的问题。

您必须熟悉MOD的以下属性:

属性 1:(a*b*c*d...*p*q) % MOD = (a%MOD)(b%MOD)(c%MOD) .....(q%MOD);

但 LCM 的情况并非如此。

LCM(a,b)=a*b/GCD(a,b)。

LCM(LCM(a,b),c)=LCM(a,b)*c/GCD(LCM(a,b),c)。

每当 LCM 大于 MOD 时，上述属性就会被破坏。您必须尝试仅根据分子中不同数字的乘积来找到 LCM。

这可以通过对所有数字进行因式分解并记录各种因数的最高幂来完成。

LCM = (2^a)(3^b)...现在您可以轻松地迭代它们，并使用属性 1 将限制保持在 MOD 下。