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[0];
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;
}
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
same problem with me
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
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 ??
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)}
thoda or batao…ya fr koi online resource ?