计算模数为1000000007的N个数的LCM

Question

我在LCM上解决了以下问题:计算N个模数为1000000007的LCM

我的方法:

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

只需将您的数字分解为素数数组,计算这些数组的lcms,然后将它们乘以答案.

第一个素数是2,3,5,7,11,13 ......所以,例如,45 = 3 ^ 2*5变成{0,2,1,0,0,...}

和

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