kedar1514's blog

Help me to understand why there is TLE
By kedar1514, history, 3 years ago, In English

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;	
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be because 'i' overflowed in the first case and became negative. (int overflows when i >= 50000).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That is because when you were using int, then i*i could have gone out of bounds and become negative, leading to an infinite loop. Changing to long long prevents that from happening.

→ Reply