MXLCM prime factors approach giving TLE

Here is the link to the problem :

What I have done is that first I found all the prime number from 1 to 10000 using the sieve of Eratosthenes. Then, for each element in the array (the list of n numbers), I found all the numbers in the sieve(whose elements are stored in an array) that will divide this element(the element of the array). Now, I found out the maximum power of that prime factor satisfying this. I did this for all the elements of the sieve which are smaller than this element(the element of the array). I did this for all the elements of the array, thus storing the minimum power of each prime factor required to make the LCM.
After this, I traversed from 1 to m and found out the factor with which this each number will multiply the LCM if it is included. In this process, I found out the element that will have the maximum multiplication factor. Now I am unable to think of a proper big O for my solution. Can somebody let me know if I can make any optimizations in it.

Here is my code :

/*Priyansh Agarwal*/
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long ll;
void helper(int value,int *arr,int *arr1,int counter)
{
	int i=0;
	while(i<counter && arr[i]<=value)
	{
		int it=arr1[i]+1;
		if(value%arr[i]==0)
		{
			int value1=pow(arr[i],it);
			int temp=value;
			while(true)
			{
				if(temp% value1==0)
				{
					arr1[i]++;
					value1=value1*arr[i];
				}
				else
					break;
			}
		}
		i++;
	}
}
ll helper1(int value,int*arr,int *arr1,int counter) //this function finds out the multiplication factor for the corresponding number passed to it);
{
	int i=0;
	ll sum=1;
	while(i<counter && arr[i]<=value)
	{
		int it=arr1[i]+1;
		if(value%arr[i]==0)
		{
			int value1=pow(arr[i],it);
			int temp=value;
			// ll sum=1;
			while(true)
			{
				if(temp% value1==0)
				{
					value1=value1*arr[i];
					sum=sum*ll(arr[i]);
				}
				else
					break;
			}
		}
		i++;
	}
	return sum;
}
int main()
{
	fastio();
	freopen("Input.txt","r",stdin);
	freopen("Output.txt","w",stdout);
	bool *sieve=new bool[10000+1]();
	sieve[0]=true;
	sieve[1]=true;
	sieve[2]=false;
	int *arr=new int[1230];
	int *arr1=new int[1230]();
	int counter=0;
	for(int i=2;i<=10000;i++)
	{
		if(sieve[i]==false)
		{
			arr[counter++]=i;
			for(int j=2*i;j<=10000;j+=i)
				sieve[j]=true;
		}
	}
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		for(int i=0;i<1230;i++)
			arr1[i]=0;
		cin>>n>>m;
		int *arr3=new int[n];
		bool *arr4=new bool[m+1]();
		for(int i=0;i<n;i++)
		{
			cin>>arr3[i];
			arr4[arr3[i]]=true;
			helper(arr3[i],arr,arr1,counter);
		}
		int i=0;
		// while(i<counter && arr[i]<=m)
		// {
		// 	cout<<arr[i]<<" "<<arr1[i]<<endl;
		// 	i++;
		// }
		// cout<<"asdf"<<endl;
		int max1=1;
		ll max2=1;
		for(int i=2;i<=m;i++)
		{
			if(arr4[i])
				continue;
			ll max3=helper1(i,arr,arr1,counter);
			// cout<<i<<" "<<max3<<endl;
			if(max3>max2)
			{
				max2=max3;
				max1=i;
			}
		}
		cout<<max1<<endl;
	}
	return 0;
}

Why don’t you precompute prime factors using sieve ?
AC in 0.4 secs
https://www.codechef.com/viewsolution/30809662
Because each number might appear 100 times. If you precompute it then it will be much faster.

4 Likes

Oh thanks a lot. I never thought of that. This will really optimize it to a great extent. Otherwise, the approach is fine right??

1 Like

I don’t fully understand your approach.
What I did was,
find LCM of given N integers in form of its prime factors.
Let this LCM be k.

Then for each value in 1 to M (say i), find LCM(k,i)/k ( Basically find difference b/w powers of prime factors of i ). Output smallest index with highest value.

5 Likes

Access Denied?

1 Like

check now

Well, that is exactly what I have done. But I got your point, I should pre-compute those prime factors.

1 Like

can someone tell me how to overcome the overflow
like i do brute force and i knw if all are prime it wil store so wht is the approach for find lcm of whole array

I think in you code
for(j=i;j<10001;j+=i){
tmp[i]=true;
v[j].push_back(i);
}
It should tmp[j]=true instead of tmp[i].

Why brute force did not work in this problem although by looking at the constraints, it was like that bruteforce can give me full points. Although I came with this solution also but not understand why brute force didnt work?

M = 10^4, If you have like say 10 big prime numbers near to 10^4, LCM would overflow.

Bro, as you can see the question asks you to find the number that needs to be added to the array to maximize the LCM. You clearly don’t necessarily have to find the actual LCM to do that. So, actually finding the LCM is not how you will be able to do it. Try finding the LCM of all numbers from 1 to 10000 and you will find out that this cant even be stored in long long in C++. Plus there is a huge complexity linked to this thing as each time your LCM will increase at a very rapid rate.

1 Like

I did not understand what are you saying, if overflow then WHY TLE not RUNTIME?

TLE would be caused if you are being inefficient in calculating prime factors.

Why is this wrong? Solution: 30841443

you are absolutely correct XD
But its still N*log(N) so works.

but if do find lcm for 1 to 10000still overflow occurs
pls elaborate

It would be very great if you explain with an example because I m a python coder I didn’t fully understand by your solution but your approach looks kinda easier

1 Like

overflow

1 Like

where?