Help needed March Lunchtime - MAXLCM

1

Hey i am not getting the test case where my code is going wrong .

#define loop(i,n) for(int i=0;i<n;i++)
using namespace std;
int getlcm(int* ar,int n){
    int lcm = ar[0];
    for(int i=1 ;i<n;i++){
        lcm = (ar[i]*lcm)/__gcd(lcm,ar[i]);
    }
    return lcm; 
}
int getmaxlcm(int lcm,int m,int* ar,int n){
    //int val= *min_element(ar,ar+n);
    int val=1;
    for(int i=1;i<=m;i++){
        int ans = (i*lcm)/__gcd(i,lcm);
        if(ans > lcm){
            val = i;
        }
    }
    return val;
}
int main(void){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int* ar = new int[n];
        loop(i,n){
            cin>>ar[i];
        }
        int lcm = getlcm(ar,n);
        int maxlcm = getmaxlcm(lcm , m,ar,n);
        cout<<maxlcm<<endl;
    }
  return 0;
}
1 Like
2

> lcm is overflowing, you can’t take the multiplication of all the number

3

I did the same, but getting wrong answer. Can anyone tell me why?
Here is my code:

#include<bits/stdc++.h>
#define int long long int
#define f(i,s,e) for(i=s;i<e;++i)

int lcm(int a,int b)
{
    return (a*b)/__gcd(a,b);
}

signed main(void)
{
    Arena
    register int i,j,num,z,t=1;
    cin>>t;
    f(z,1,t+1)
    {
        int n,m;cin>>n>>m;
        int prev;cin>>prev;
        f(i,1,n)
        {
            cin>>num;
            prev=lcm(prev,num);
        }
        int mi=prev,p=1;
        f(i,2,m+1)
        {
            int x=lcm(prev,i);
            if(x>mi)
            {
                mi=x;p=i;
            }
        }
        cout<<p<<endl;
    }
    return 0;
}
4

lcm will give wrong answer, integer overflow

5

Can u tell correct approach for this

6

so what can we do here ? even long long is not working .

7

U should change Ur approach

8

image
image481×632 32 KB

here vec will keep the maximum number of occurance of any prime factor can have in the overall lcm
then iterate over m and check what is maximum value any particular integer can offer in the vec, to make it possible maximum

1 Like
9

Thanks