Doubt - MXMLCM

3

same problem with me

1 Like
4

LCM overflow when all are prime numbers thats why

3 Likes
5

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
6

Atleast for 50 points it should accept

1 Like
7

As n and m is 100 right

8

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

9

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

10

Got it do u get solution for it

11

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.

12

Ok can u tell approach for it

13

pretty sure itss lcm by prime factorization

14

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

15

It won’t work I think

16 
#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?

17

Why would it not overflow ??

1 Like
18

no… actually i think i aplplied boost so…leave …how to find lcm of array by prime factorization…plz give me brief idea :pray:

19

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
20

thoda or batao…ya fr koi online resource ?

21

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

22

please see this it will clear your doubt