CODEWITHSUNDEEP
c++algorithmlcm
Ritesh Kumar Gupta
Ritesh Kumar Gupta

Reputation: 5191

Calculate LCM of N numbers modulo 1000000007

I was solving following problem on LCM : Calculate LCM of N numbers modulo 1000000007

My approach :

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

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

Thanks!

Upvotes: 1

Views: 7799

Answers (4)

Steven Anderson
Steven Anderson

Reputation: 75

The correct approach would be to prime factorize the elements of the array and keep track of the highest power of every prime for each element. LCM will be the product of these primes raised to their highest power in the array.

Upvotes: 2

Sushil Kumar
Sushil Kumar

Reputation: 125

your approach is wrong as mentioned by johnchen902.

Here is my approach:

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

SEE AT IDEONE

Upvotes: 5

Artem Volkhin
Artem Volkhin

Reputation: 1372

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;
}

Upvotes: 5

johnchen902
johnchen902

Reputation: 9601

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

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.

ALSO AT IDEONE

Upvotes: 6

Related Questions