c++ - 以 1000000007 为模计算 N 个数字的 LCM

Question

我在 LCM 上解决了以下问题：Calculate LCM of N numbers modulo 1000000007

我的方法：

typedef unsigned long long ull;
const ull mod=1000000007;
ull A[10009];
/*Euclidean GCD*/
ull gcd(ull a,ull b)
{
    while( b != 0)
    {
        ull  t = b;
        b= a %t;
        a = t;
    }
    return a;
}
ull lcm(ull a, ull b) 
{ 
    return (a/gcd(a,b))%mod*(b%mod); 
}
ull lcms(int  l ,ull * A)
{
    int     i;
    ull result;
    result = 1;
    for (i = 0; i < l; i++) 
        result = lcm(result, A[i])%1000000007;
    return result;
}
int main()
{
    int T;
    cin>>T;
    while(T--)/*Number of test cases*/
    {
        int N;
        cin>>N;/*How many Numbers in Array*/
        for(int i=0;i<N;++i)
        {
            cin>>A[i];//Input Array
        }
        cout<<lcms(N,A)%1000000007<<endl;
    }
    return 0;
}

当我提交我的解决方案时，我得到了错误的答案。约束是：

1<=N<=1000
and 1<=A[i]<=10000

在 IDEONE

我想我因为溢出而得到错误的答案。如何改进我的代码？

谢谢！

Answer 1

1000000007太大了，我无法举个例子。让我举个17例子：

LCMS(10, 9, 8) % 17 =
LCM(10, LCM(9, 8)) % 17 =
LCM(10, 72) % 17 =
360 % 17 =
3

这就是您的代码所做的：

LCMS(10, 9, 8) % 17 =
LCM(10, LCM(9, 8) % 17) % 17 =
LCM(10, 72 % 17) % 17 =
LCM(10, 4) % 17 =
40 % 17 =
6

这是错误的。

也在 IDEONE

Answer 2

Just factorize your numbers into arrays of prime numbers, calculate lcms over these arrays and then multiply them back into answer.

first primes are 2, 3, 5, 7, 11, 13, .. so, for example, 45 = 3^2 * 5 turns into {0, 2, 1, 0, 0, ...}

and

vector<uul> lcm(vector<uul> a, vector<uul> b) {
  vector<uul> res(a.size());
  for (size_t i = 0; i < a.size(); ++i) {
    res[i] = max(a[i], b[i]);
  }
  return res;
}

Answer 3

如johnchen902所述，您的方法是错误的。

这是我的方法：

for i=1 to n
    a.take i_th number as x
    b.reduce(devide) remaining numbers(i+1_th to n_th) by their gcd with x
    c.multiply x to ans and take mod of ans
return ans

见 IDEONE

Answer 4

正确的方法是对数组的元素进行素数分解，并跟踪每个元素的每个素数的最高幂。LCM 将是这些素数的乘积，它们在阵列中被提升到最高功率。