MXLCM prime factors approach giving TLE

general
27
28

have a look at this

29
30

please take a look at this

31

Oops! That page doesn’t exist or is private.

1 Like
32
1 Like
33

#include
using namespace std;

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

long long int lcm(long long int a[],long long int n)
{
long long int ans = a[0];

for (long long int i = 1; i < n; i++) 
{
    ans = (a[i] * ans)/ (gcd(a[i], ans)); 
}
return ans;

}

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
long long int n,m;
cin>>n>>m;

    long long int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    long long int ans=lcm(a,n);
    long long int max=ans;
    long long int num=1;

    for(long long int i=2;i<=m;i++)
    {
        long long int cur=(i*ans)/(gcd(i,ans));
        if(cur>max)
        {
            max=cur;
            num=i;
        }
    }
    cout<<num<<endl;
    
}
return 0;

}
can you help to find the error in this?

34
35

LCM overflows range of int. Store prime factorization instead.

36

have a look here

37

look at this

38

here take a look at this please

39

beautiful approach,i must say!

2 Likes
40

Thank you, till now i got the point but now how will you find the smallest no… I guess your approach should be traverse from 1 to m and for each no. find the prime factors and multiply with original lcm ???

1 Like
41

Can Somebody Explain why my code giving WA ??
Submission Link

Edit : Figured Out Integer Overflow

42

Can you link somewhere I can read this pre computing algo. I usually use the j = i*i ; j += i sieve, which I think doesnt work here.

43

Do not multiply. Just see which values are gonna change in previous LCM.
And select the one with Maximum change and minimum value

44

You can run the code, observer and see the difference b/w them.

45

lcm can be too big to be stored in for any datatype, thats why

46

I am using SPF (shortest prime factor) SIEVE in nlog(logn), and log(n) for any query afterwards,
Here’s the code : CodeChef: Practical coding for everyone