kedar1514's blog

By kedar1514, history, 4 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;	
}

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it