我解决下LCM问题：N 的计算LCM数模1000000007

I was solving following problem on 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;
}

我收到错误答案时，我提出我的解决方案。 约束条件是：

I am getting Wrong Answer when I submit my solution. The constraints are:

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

AT IDEONE

AT IDEONE

我想我得到，因为溢出的错误答案。我怎样才能提高我的code？

I guess I am getting Wrong Answer because of Overflow. How can I improve my Code?

谢谢！

推荐答案

1000000007 是太大了，我以一个例子。让我用 17 例如：

1000000007 is too big for me to take as an example. Let me use 17 for example:

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

这是你的code做的：

This is what your code doing:

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

这是错误的。

Which is wrong.

也在IDEONE

ALSO AT IDEONE