# MXLCM prime factors approach giving TLE

Can Somebody Explain why my code giving WA ??

Edit : Figured Out Integer Overflow

Can you link somewhere I can read this pre computing algo. I usually use the j = i*i ; j += i sieve, which I think doesnt work here.

Do not multiply. Just see which values are gonna change in previous LCM.
And select the one with Maximum change and minimum value

You can run the code, observer and see the difference b/w them.

lcm can be too big to be stored in for any datatype, thats why

I am using SPF (shortest prime factor) SIEVE in nlog(logn), and log(n) for any query afterwards,
Here’s the code : CodeChef: Practical coding for everyone

Going by intuition I thought that the answer should be the prime number just below or equal to M(because that would straight away be multiplied to the LCM) . But this didn’t worked

vll =vector of long long int
vpl =vector of pll

Can you please explain the logic. I know calculating LCM will overflow. I know prime calculation.
Then No idea how to find biggest number.

Help Please. Why itis giving TLE.

#include<bits/stdc++.h>
#define ll long long int
#define pll pair <ll,ll>
#define vll vector
#define vpl vector
#define s second
#define f first

using namespace std;

int temp;
vll primes;
vpl vec[10001];
void f()
{
ll arr[10001]={0};
ll z=sqrt(10001);
for(ll i=2;i<z;i++)if(!arr[i]){primes.push_back(i);for(ll j=i;j<10001;j+=i)if(!arr[j])arr[j]=i;}
for(ll i=2;i<10001;i++)if(!arr[i]){primes.push_back(i);arr[i]=i;}
for(ll i=2;i<10001;i++)
{
ll n=i,c;
while(n>1)
{
temp=arr[n];
c=0;
while(n%temp==0)n/=temp,++c;
vec[i].push_back(make_pair(temp,c));
}
}
}
vpl lcm(vpl a,vpl b)
{
ll n=a.size(),m=b.size();
vpl z;
for(ll i=0,j=0;i<n || j<m;)
{
if(i<n && j<m){
if(a[i].f==b[j].f)z.push_back(make_pair(a[i].f,max(a[i].s,b[j].s))),i++,j++;
else if(a[i].f<b[j].f)z.push_back(a[i]),i++;
else z.push_back(b[j]),j++;
}
else if(i<n)z.push_back(a[i]),i++;
else if(j<m)z.push_back(b[j]),j++;
else break;
}
return z;
}

ll power(ll n,ll m)
{
if(m==0)return 1;
ll z=power(n,m>>1);
z*=z;
if(m&1)z*=n;
return z;
}

ll hcf(ll a,vpl b)
{
ll n=vec[a].size(),m=b.size();
ll ans=1;
for(ll i=0,j=0;i<n && j<m;)
{
if(vec[a][i].f==b[j].f)ans*=power(vec[a][i].f,min(vec[a][i].s,b[j].s)),i++,j++;
else if(vec[a][i].f<b[j].f)i++;
else j++;
}
return a/ans;
}

vpl find(ll arr[],ll start,ll end)
{
if(start==end)return vec[arr[start]];
ll mid=(start+end)>>1;
return lcm(find(arr,start,mid),find(arr,mid+1,end));
}

void solve()
{
ll n,m;
cin>>n>>m;
ll arr[n];
vpl z;
for(ll i=0;i<n;i++)cin>>arr[i];
z=find(arr,0,n-1);

ll maxy=1;
ll multi=1;ll ans=1;
ll p=primes.size();
for(ll i=2;i<=m;i++)
{
multi=hcf(i,z);
if(multi>maxy)maxy=multi,ans=i;
}

cout<<ans<<"\n";

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
f();
int t;
cin>>t;
while(t–)solve();
return 0;
}

Thanks for the explanation Very well put.

can you please elaborate your solution i am not able understand the solution.