# Doubt - MXMLCM

Why applying brute force approach like this, gives wrong answer?

``````while(t--){
int n,m,num;
cin >> n >> m;

fo(i,n) cin >> a[i];

ll mx=a;
Fo(i,1,n){
mx=(mx*a[i])/(__gcd(mx,a[i]));
}

int ans=1;
ll res=mx;
for(ll i=2;i<=m;i++){
ll newmx=(res*i)/__gcd(i,res);
if(newmx>mx){
mx=newmx;
ans=i;
}
}

cout << ans << endl;
}
``````
2 Likes

Same problem here.i too approached same way but got wrong answer I read nearly of 30 times question but I could not interested why it is going wrong

1 Like

same problem with me

1 Like

LCM overflow when all are prime numbers thats why

3 Likes

I was thinking the same but the problem here is your mx variable will overflow for any data type because a[i] can be of order 10^4 and n is of order 10^4. if many numbers in array are prime then it will overflow.

2 Likes

Atleast for 50 points it should accept

1 Like

As n and m is 100 right

I returned -1 on -ve lcm value, and it showed NZEC error for 1st subtask too. Used long long instead of int

No it shouldn’t ,you can’t store numbers of order 100^{100} in any data type

Got it do u get solution for it

Logically, there are 25 prime numbers in the range of 1 to 100 and the number of prime numbers greater than 10 in this range is 21. Hence 10^21 exceeds the long long int range. So overflow. By the way we are not even considering the composite numbers from 1 to 100 which are in turn combination of these prime numbers which might increase the limit further.

Ok can u tell approach for it

pretty sure itss lcm by prime factorization

Is brute force finding the highest number less than m which won’t divide any of the integers present in array, or else 1?

It won’t work I think

``````#include <bits/stdc++.h>
#include <boost/math/common_factor.hpp>
using namespace std;
#define lli long long int
int main() {
lli t;
cin>>t;
while(t--){
lli n,m;
cin>>n>>m;
lli a[n];
for(lli i=0;i<n;i++) cin>>a[i];
lli lcmm=a;
for(lli i=0;i<n;i++){
lcmm = boost::math::lcm(lcmm,a[i]);
}
lli maxi =lcmm;
lli val=1;
for(lli i=1;i<=m;i++){
lli nlcm = boost::math::lcm(lcmm,i);
if(maxi<nlcm){
maxi = nlcm;
val=i;
}
}
cout<<val<<endl;
}
return 0;
}
``````

Why this gives wrong answer @l_returns is the boost lcm fucntion can overflow?

Why would it not overflow ??

1 Like

no… actually i think i aplplied boost so…leave …how to find lcm of array by prime factorization…plz give me brief idea LCM ( p_1^{a} * p_2^{b} , p_1^{c} * p_2^{d} ) = p_1^{max(a,c)} * p_2^{max(b,d)}

2 Likes

thoda or batao…ya fr koi online resource ?