# Doubt - MXMLCM

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[0];
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 ?

Find prime factorization of each number.

``````20 75 72 13
``````

=>
(2^2 * 5^1) , (3^1*5^2), (2^3*3^2), (13^1)
Find max power of 2, max power of 3, max power of 5 and so on for each prime number.
=> LCM = 2^3 * 3^2 * 5^2 * 13^1

please see this it will clear your doubt