math - n 个数模 1000000007 的 LCM

Question

我必须找到n个数字的LCM MODULO 10 ^ 9 + 7。我的方法是找到两个数字的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 下。

Answer 2

仅供将来参考，这是一个不使用素数分解的 C++ 实现。

一种可能的解决方案是为答案保留一系列因素。每个因子将是 1..N 中的每个数字，除以 GCD(数字，[所有以前的数字])。为此，您必须编写一个特殊的 GCD 来计算单个数字和一个因子数组之间的结果。这段 C++ 代码展示了它是如何工作的：

#include <iostream>
#include <vector>
#define lli long long int
using namespace std;

vector<lli> T;

lli gcd(lli a, lli b) {
    if(b == 0) 
        return a;
    return gcd(b, a%b);
}

lli gcd_vector(vector<lli>& a, lli b) {
    lli ma = 1;
    for(int i=0; i<T.size(); i++)
        ma = ma*T[i]%b;
    return gcd(b, ma);
}

int main() {
    lli answer = 1;
    for(int i=1; i<=1000; i++) {
        lli factor = i/gcd_vector(T, i); 
        T.push_back(factor);
        answer = (answer*factor)%1000000007;
    }

    cout << answer << endl;
}