Help me to understand why there is TLE

Revision en2, by kedar1514, 2021-05-27 22:47:10

I was solving a div 3 problem Common Divisors while solving this problem the below code got TLE. Submission URL for below code

void solve()
{
	long long n;
	cin>>n;
	vector<long long> arr(n);
	for (int i = 0; i < n; ++i) cin>>arr[i];
 
	long long num = arr[0];
 
	for (int i = 0; i < n; ++i)
	{
		num = __gcd(num,arr[i]);
	}
	
	long long count = 0;
	for (int i = 1; i*i<=num; ++i)
	{
		if(num%i==0){
			if(num/i==i)
				count++;
			else
				count+=2;
		}
	}
	cout<<count<<endl;	
}

But after changing int i to long long i in 2nd for loop it worked fine. see below code for changes Submission URL for below code

void solve()
{
	long long n;
	cin>>n;
	vector<long long> arr(n);
	for (int i = 0; i < n; ++i) cin>>arr[i];
 
	long long num = arr[0];
 
	for (int i = 0; i < n; ++i)
	{
		num = __gcd(num,arr[i]);
	}
	
	long long count = 0;
	for (long long i = 1; i*i<=num; ++i) // changed int i to long long i
	{
		if(num%i==0){
			if(num/i==i)
				count++;
			else
				count+=2;
		}
	}
	cout<<count<<endl;	
}
Tags #tle, #maths, #cpp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kedar1514 2021-05-27 22:47:10 4 Tiny change: 'ong long int i** in 2n' -> 'ong long i** in 2n'
en1 English kedar1514 2021-05-27 22:45:32 1317 Initial revision (published)