Doubt - MXMLCM

same problem with me

1 Like

LCM overflow when all are prime numbers thats why


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.


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;
    lli 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);
        maxi = nlcm;
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 :pray:

LCM ( p_1^{a} * p_2^{b} , p_1^{c} * p_2^{d} ) = p_1^{max(a,c)} * p_2^{max(b,d)}


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