Kn0wthyself's blog

Number of common divisors
By Kn0wthyself, history, 10 months ago, In English

Today I am share my new experience . I am trying to solve a problem in SPOJ. Problem link:https://www.spoj.com/problems/COMDIV/ When I solve this problem using C++ it gives TLE for simple code. For this problem my solving approach was at first find the GCD of two values than from 1 to GCD I use a loop if any number is divided by that than i count it for two time without corner case. But it gives me Time Limited Exceed. I really become astonished to see this. Than just i convert it into c . instead of cin use scanf and instead of cout use printf than it accept the code. Truly it was a bad experience for me in problem solving.

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just number of divisors of gcd

Spoiler
→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This will give you TLE 

    #include<bits/stdc++.h>
using namespace std;

void solve(int a){
    int c=0;
    for(int i=1;i<sqrt(a);i++){
            if(a%i==0){
                if(a/i==i)c++;
                else c+=2;
            }
    }
    cout<<c<<endl;
}
int gcd(int a,int b)
{
	if(a==0)
		return b;
	return gcd(b%a,a);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int l,m;
        cin>>l>>m;
        int a=gcd(l,m);
        solve(a);
    }
}
    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yeah because that's sqrt(1e6) * 1e6 = 1e9

      learn sieve of eratosthenes

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh! Thanks! I didn’t think that way. My pleasure for your instruction.

        → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But i have a question why this this solution excepted 

        #include <stdio.h>
int gcd(int a,int b)
{
	
	if(a==0)
		return b;
	return gcd(b%a,a);
}
int main(void) {
	int t;
	scanf("%d",&t);
	for(int j=0;j<t;j++)
	{
		int a,b,cd=0;
		scanf("%d%d",&a,&b);
		int n = gcd(a,b);
		for(int i=1;i*i<=n;i++)
		{
			if(n%i==0)
			{
				if(n/i==i)
					cd+=1;
				else
					cd+=2;
			}
		}
		printf("%lld\n",cd);
	}
	return 0;
}
        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          luck? dunno, there's still a simple solution that passes comfortably.

          → Reply